Submission #123980

#TimeUsernameProblemLanguageResultExecution timeMemory
123980songcMeetings (JOI19_meetings)C++14
100 / 100
1315 ms1084 KiB
#include <bits/stdc++.h> #include "meetings.h" using namespace std; typedef long long LL; typedef pair<int, int> pii; vector<int> adj[2020]; vector<int> V[2020]; bool chk[2020]; void f(int u){ if (V[u].size() <= 1) return; vector<int> P = V[u]; V[u].clear(); int v = P[rand() % P.size()]; while (v == u) v = P[rand() % P.size()]; vector<int> S; S.push_back(u); V[u].push_back(u); S.push_back(v); V[v].push_back(v); for (int w : P){ if (w == u || w == v) continue; int ret = Query(u, v, w); V[ret].push_back(w); S.push_back(ret); } sort(S.begin(), S.end()); S.erase(unique(S.begin(), S.end()), S.end()); sort(S.begin(), S.end(), [&](int a, int b){ if (a == u || b == v) return true; if (a == v || b == u) return false; return Query(a, b, u) == a; }); for (int i=0; i<(int)S.size()-1; i++){ if (S[i] < S[i+1]) Bridge(S[i], S[i+1]); else Bridge(S[i+1], S[i]); } for (int w : S) f(w); } void Solve(int N) { for (int i=0; i<N; i++) V[0].push_back(i); f(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...