# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1085878 | anastasiskolio | Drivers (BOI24_drivers) | C++14 | 158 ms | 21548 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAXN 200000
#define MAXM 200000
#define MAXU 200000
using namespace std;
vector<array<int, 3>> edges(MAXM);
vector<array<int, 4>> queries(MAXU);
vector<int> parent(MAXN), comp_size(MAXN);
vector<string> ans(MAXU);
int N, M, U;
void disjointSets() {
for (int a = 0; a < N; a++) {
parent[a] = a;
comp_size[a] = 1;
}
}
int find(int a) {
return a == parent[a] ? a : parent[a] = find(parent[a]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (comp_size[a] < comp_size[b])
swap(a, b);
parent[b] = a;
comp_size[a] += comp_size[b];
}
}
int main() {
scanf("%d %d %d", &N, &M, &U);
for (int i = 0; i < M; i++) {
scanf("%d %d %d", &edges[i][1], &edges[i][2], &edges[i][0]);
--edges[i][1];
--edges[i][2];
}
for (int i = 0; i < U; i++) {
scanf("%d %d %d", &queries[i][1], &queries[i][2], &queries[i][0]);
--queries[i][1];
--queries[i][2];
queries[i][3] = i;
}
sort(edges.begin(), edges.begin() + M);
sort(queries.begin(), queries.begin() + U);
disjointSets();
int j = 0;
for (int i = 0; i < U; i++) {
while (j < M && edges[j][0] <= queries[i][0]) {
unite(edges[j][1], edges[j][2]);
++j;
}
ans[queries[i][3]] = find(queries[i][1]) == find(queries[i][2]) ? "TAIP" : "NE";
}
for (int i = 0; i < U; i++)
printf("%s\n", ans[i].c_str());
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |