글 읽기 - 시간초과 질문 c++

gksthdgns3 2년 전 0

왜 시간초과가 나는 걸까요?

#include<bits/stdc++.h>
using namespace std;

int parent[1000001];
vector<pair<pair<int, int>,int>> v;


int doFind(int x) {
	if (parent[x] == x)return x;
	return parent[x] = doFind(parent[x]);
}

void doUnion(int x, int y) {
	int px = doFind(x);
	int py = doFind(y);

	if (px > py) {
		parent[py] = px;
	}
	else {
		parent[px] = py;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, q;	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
		int x1, x2, y;	cin >> x1 >> x2 >> y;
		v.push_back({ {x1,x2},i });;
	}
	sort(v.begin(), v.end());
	
	for (int i = 0; i < n-1;) {
		for (int j = i+1; j < n;) {
			if (v[j].first.first <= v[i].first.second) {
				doUnion(v[i].second, v[j].second);
				j++;
			}
			else {
				i++;
				break;
			}	
		}
	}
	
	int a, b;
	for (int i = 0; i < q; i++) {
		cin >> a >> b;
		if (doFind(a) == doFind(b)) {
			cout << 1 << "\n";
		}
		else {
			cout << 0 << "\n";
		}
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문 c++

gksthdgns3 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말