제출 #838707

#제출 시각아이디문제언어결과실행 시간메모리
838707JohannSimurgh (IOI17_simurgh)C++14
0 / 100
82 ms6628 KiB
#include "simurgh.h" #include "bits/stdc++.h" using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef vector<pii> vpii; typedef vector<vpii> vvpii; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() int N; vi U, V; vvpii adj; vvi adjmat; vi deg; queue<int> todo; vi goldenTree; const int NOTHING = 0; const int FRONTIER = 1; const int EXPLORED = 2; vi tmpTree; int cntQueries; vi askEdges; void addEdge(int e) { goldenTree.push_back(e); assert(deg[U[e]] > 0 && deg[V[e]] > 0); --deg[U[e]], --deg[V[e]]; if (deg[U[e]] == 1) todo.push(U[e]); if (deg[V[e]] == 1) todo.push(V[e]); } void linearSearch(int v, vi &neighbors, vi &candidates) { if (neighbors.empty() || candidates.empty()) return; if (sz(candidates) == 1) addEdge(adjmat[v][candidates[0]]); else { tmpTree = vi(all(goldenTree)); for (int i = 0; i < sz(neighbors) - 1; ++i) tmpTree.push_back(adjmat[neighbors[i]][neighbors[i + 1]]); vi ans; for (int i = 0; i < sz(candidates); ++i) { int u = candidates[i]; tmpTree.push_back(adjmat[v][u]); ans.push_back(count_common_roads(tmpTree)); ++cntQueries; tmpTree.pop_back(); } int maxi = *max_element(all(ans)); assert(count(all(ans), maxi) == 1); for (int i = 0; i < sz(candidates); ++i) if (ans[i] == maxi) { addEdge(adjmat[v][candidates[i]]); return; } assert(false); } } void findEdge(int v) { vi neighbors; for (pii e : adj[v]) if (deg[e.first] > 0) neighbors.push_back(e.first); if (sz(neighbors) <= 3) { linearSearch(v, neighbors, neighbors); return; } tmpTree = vi(all(goldenTree)); int sq = 2; while ((sq + 1) * (sq + 1) < sz(neighbors)) ++sq; vvi groups(sq + 1); // groups[sq] is for the rest for (int i = 0; i < sq * sq; ++i) groups[i % sq].push_back(neighbors[i]); for (int i = sq * sq; i < sz(neighbors); ++i) groups[sq].push_back(neighbors[i]); for (int j = 0; j < sz(groups); ++j) for (int i = 0; i < sz(groups[j]) - 1; ++i) tmpTree.push_back(adjmat[groups[j][i]][groups[j][i + 1]]); if (!groups.back().empty()) tmpTree.push_back(adjmat[v][groups.back().back()]); vi ans; for (int j = 0; j < sq; ++j) { for (int i = 0; i < sq; ++i) tmpTree.push_back(adjmat[v][groups[i][j]]); ans.push_back(count_common_roads(tmpTree)); ++cntQueries; for (int i = 0; i < sq; ++i) tmpTree.pop_back(); } int mini = *min_element(all(ans)); int maxi = *max_element(all(ans)); vi cand; if (maxi != mini) { assert(count(all(ans), maxi) == 1); // search further for (int j = 0; j < sq; ++j) if (ans[j] == maxi) { for (int i = 0; i < sq; ++i) cand.push_back(groups[i][j]); linearSearch(v, neighbors, cand); return; } assert(false); } else { // bruteforce groups.back() assert(!groups.back().empty()); linearSearch(v, neighbors, groups.back()); } } std::vector<int> find_roads(int n, std::vector<int> _U, std::vector<int> _V) { N = n; U = _U, V = _V; adj = vvpii(N); adjmat = vvi(N, vi(N, -1)); for (int i = 0; i < sz(U); ++i) { adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i}); adjmat[U[i]][V[i]] = adjmat[V[i]][U[i]] = i; } deg.resize(n); for (int v = 0; v < n; ++v) { vi q; for (pii e : adj[v]) q.push_back(e.second); deg[v] = count_common_roads(q); if (deg[v] == 1) todo.push(v); } goldenTree.clear(); while (!todo.empty()) { assert(cntQueries <= 12000); int v = todo.front(); todo.pop(); findEdge(v); } // cout << cntQueries << endl; return goldenTree; }
#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...