Submission #143286

#TimeUsernameProblemLanguageResultExecution timeMemory
143286tpoppoSplit the Attractions (IOI19_split)C++14
40 / 100
1241 ms16376 KiB
#include "split.h" #include<bits/stdc++.h> #define lsb(x) (x&(-x)) using namespace std; const int MAXN = 2e5 + 100; using pii = pair<int,int>; pii ord[3]; vector<int> res; vector<int> grafo[MAXN]; vector<pii> edge; int n; int parent[MAXN]; int find(int id){ if(parent[id] == id) return id; return parent[id] = find(parent[id]); } bool merge(int a,int b){ a = find(a); b = find(b); if(a == b) return false; parent[a] = b; return true; } void random_st(){ for(int i=0;i<n;i++){ grafo[i].clear(); parent[i] = i; } random_shuffle(edge.begin(),edge.end()); for(auto el : edge){ //cout<<el.first<<" "<<el.second<<endl; if(merge(el.first,el.second)){ grafo[el.first].emplace_back(el.second); grafo[el.second].emplace_back(el.first); } } } int block; int req; int rval; int rid; int dfs(int id,int prev){ //cout<<prev<<" => "<<id<<endl; if(id == block) return 0; int sum = 1; for(auto el : grafo[id]){ if(el != prev){ sum += dfs(el,id); } } if(sum >= req && sum < rval){ rval = sum; rid = id; } return sum; } int p1,p2; void f(int id,int prev,int stato){ if(id == p1) stato = 1; if(id == p2) stato = 2; switch(stato){ case 1: if(ord[0].first){ ord[0].first--; res[id] = ord[0].second; } break; case 2: if(ord[1].first){ ord[1].first--; res[id] = ord[1].second; } break; } for(auto el : grafo[id]){ if(el != prev){ f(el,id,stato); } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { res.resize(n); ::n = n; ord[0] = {a, 1}; ord[1] = {b, 2}; ord[2] = {c, 3}; sort(ord,ord + 3); edge.reserve(p.size()); for(int i=0;i<p.size();i++){ edge.emplace_back(p[i],q[i]); } for(int _=0;_<50;_++){ random_st(); int root = rand()%n; rval = rid = 1e9; block = -1; req = ord[0].first; dfs(root,-1); //cout<<rid<<" - "<<rval<<endl; if(rval == 1e9) continue; p1 = rid; rval = rid = 1e9; block = p1; req = ord[1].first; dfs(root,-1); //cout<<rid<<" - "<<rval<<endl; p2 = rid; //cout<<root<<" "<<p1<<" "<<p2<<endl; if(p2 != 1e9){ f(root,-1,0); for(auto&el:res){ if(!el) el = ord[2].second; } return res; } } return res; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p.size();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...