제출 #378271

#제출 시각아이디문제언어결과실행 시간메모리
378271pit4hMeetings (JOI19_meetings)C++14
7 / 100
1006 ms262148 KiB
#include "meetings.h" #include<bits/stdc++.h> using namespace std; int n; int RAND(int l, int r, mt19937 rng) { return uniform_int_distribution<int>(l, r)(rng); } void solve(vector<int> v, mt19937 rng) { if((int)v.size()<=1) return; if((int)v.size()==2) { //cerr<<"bridge: "<<v[0]<<' '<<v[1]<<'\n'; Bridge(min(v[0], v[1]), max(v[0], v[1])); return; } int sz = v.size(); int v1 = RAND(0, sz-1, rng), v2 = RAND(0, sz-2, rng); if(v2>=v1) v2++; //cerr<<"solve ["; /*for(int i=0; i<sz; ++i) { cerr<<v[i]; if(i<sz-1) cerr<<' '; else cerr<<"] "; } cerr<<v[v1]<<' '<<v[v2]<<" "<<n<<'\n'; */ vector<vector<int>> vec(n); vec[v[v1]].push_back(v[v1]); vec[v[v2]].push_back(v[v2]); vector<int> path = {v[v1], v[v2]}; for(int i=0; i<sz; ++i) { if(i == v1 || i==v2) continue; int u = Query(v[v1], v[v2], v[i]); //cerr<<v[i]<<": "<<u<<'\n'; if(u == v[i]) { path.push_back(v[i]); } vec[u].push_back(v[i]); } if((int)path.size() == 3) { //cerr<<"Bridge: "<<v[0]<<' '<<path[2]<<'\n'; //cerr<<"Bridge: "<<v[1]<<' '<<path[2]<<'\n'; Bridge(min(v[v1], path[2]), max(v[v1], path[2])); Bridge(min(v[v2], path[2]), max(v[v2], path[2])); } else { solve(path, rng); } for(int i=0; i<n; ++i) { //cerr<<' '<<i<<" - "<<vec[i].size()<<'\n'; solve(vec[i], rng); } } void Solve(int N) { n = N; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<int> v; for(int i=0; i<N; ++i) { v.push_back(i); } solve(v, rng); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...