제출 #1257474

#제출 시각아이디문제언어결과실행 시간메모리
1257474MercubytheFirstIsland Hopping (JOI24_island)C++20
2 / 100
1 ms428 KiB
#include <bits/stdc++.h> #include "island.h" using namespace std; struct DSU { vector<int> dsu; DSU(int n) : dsu(n+1, -1) { } int get(int x) { if(dsu[x] < 0) { return x; } return get(dsu[x]); } bool merge(int x, int y) { // merge x to y x = get(x), y = get(y); if(x == y) { return false; } dsu[y] += dsu[x]; dsu[x] = y; return true; } }; void solve(int N, int L) { vector<int> by_one {1}, order(N+1, -1); order[1] = 0; for(int i = 1; i < N; ++i) { by_one.push_back(query(1, i)); order[by_one.back()] = i; } vector<int> par(N+1, -1); DSU dsu(N); for(int i = 2; i <= N; ++i) { int cnt = 1; while(par[i] == -1) { const int x = query(i, cnt); if(order[x] < order[i]) { assert(dsu.merge(i, x)); par[i] = x; } else { assert(dsu.merge(x, i)); par[x] = i; } cnt++; } } for(int i = 2; i <= N; ++i) { assert(par[i] != -1); answer(i, par[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...