Submission #1257488

#TimeUsernameProblemLanguageResultExecution timeMemory
1257488MercubytheFirstIsland Hopping (JOI24_island)C++20
65 / 100
3 ms416 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 my_assert(bool x) { if(!x) { while(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)); // cerr << "Got: " << 1 << ' ' << i << ' ' << by_one.back() << '\n'; order[by_one.back()] = i; } for(int i = 1; i <= N; ++i) { // cerr << order[i] << " \n"[i == N]; } 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); // cerr << "Got: " << i << ' ' << cnt << ' ' << x << '\n'; if(order[x] < order[i]) { // assert(dsu.merge(i, x)); dsu.merge(i, x); par[i] = x; } else { // assert(dsu.merge(x, i)); dsu.merge(x, i); par[x] = i; } cnt++; } } for(int i = 2; i <= N; ++i) { my_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...