Submission #1172457

#TimeUsernameProblemLanguageResultExecution timeMemory
1172457danglayloi1Meetings (JOI19_meetings)C++20
100 / 100
1175 ms988 KiB
#include "meetings.h" #include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); int get(int l, int r) { return l+mt()*mt()%(r-l+1); } // void Bridge(int u, int v) // { // cout<<"haha"<<u<<' '<<v<<'\n'; // } // int Query(int u, int v, int w) // { // cout<<u<<' '<<v<<' '<<w<<'\n'; // int x; // cin>>x; // return x; // } int st, en; bool cmp(int a, int b) { if(a==st) return 1; if(a==en) return 0; if(b==st) return 0; if(b==en) return 1; return Query(st, a, b)==a; } void dfs(int u, vector<int> ver) { if(ver.size()==1) return; if(ver.size()==2) { if(ver[0]>ver[1]) swap(ver[0], ver[1]); Bridge(ver[0], ver[1]); return; } shuffle(ver.begin(), ver.end(), mt); map<int, vector<int>> mp; mp.clear(); int v=u; while(v==u) { int pos=get(0, ver.size()-1); v=ver[pos]; } mp[u].emplace_back(u); mp[v].emplace_back(v); for(int x:ver) { if(x==u || x==v) continue; int nw=Query(u, v, x); mp[nw].emplace_back(x); } vector<int> path; path.clear(); for(auto it:mp) { path.emplace_back(it.fi); dfs(it.fi, it.se); } st=u, en=v; sort(path.begin(), path.end(), cmp); for(int i = 1; i < path.size(); i++) Bridge(min(path[i-1], path[i]), max(path[i-1], path[i])); } void Solve(int n) { vector<int> tmp; tmp.clear(); for(int i = 0; i < n; i++) tmp.emplace_back(i); shuffle(tmp.begin(), tmp.end(), mt); dfs(tmp[0], tmp); } // int main() // { // Solve(5); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...