Submission #1212638

#TimeUsernameProblemLanguageResultExecution timeMemory
1212638guagua0407Split the Attractions (IOI19_split)C++20
18 / 100
2005 ms17096 KiB
#pragma GCC optimize("O4") #include "split.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { auto stt=clock(); vector<pair<int,int>> vec={{a,1},{b,2},{c,3}}; sort(all(vec)); vector<vector<int>> adj(n); int m=(int)p.size(); for(int i=0;i<m;i++){ adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } vector<int> C(n,vec[2].s); vector<bool> used(n,false); mt19937 rng(time(NULL)); vector<int> st; vector<int> st2; for(int i=0;i<n;i++){ shuffle(all(adj[i]),rng); } while(clock()-stt<1.98*CLOCKS_PER_SEC){ int t; function<void(int,int)> dfs2=[&](int v,int p){ //cout<<v<<' '<<p<<'\n'; st.push_back(v); used[v]=true; if((int)st.size()==t) return; //shuffle(all(adj[v]),rng); for(auto u:adj[v]){ if(u==p or used[u]) continue; dfs2(u,v); if((int)st.size()==t) return; } }; used=vector<bool>(n,false); t=vec[0].f; int x=abs((int)rng())%n; dfs2(x,-1); st2=st; st.clear(); t=n; for(int x=0;x<n;x++){ if(used[x]) continue; dfs2(x,-1); if((int)st.size()<vec[1].f){ st.clear(); } else{ break; } } if(st.empty()) continue; for(auto v:st2){ C[v]=vec[0].s; } for(int i=0;i<vec[1].f;i++){ C[st[i]]=vec[1].s; } return C; } return vector<int>(n,0); } /* 6 5 2 2 2 0 1 1 2 2 3 3 4 4 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...
#Verdict Execution timeMemoryGrader output
Fetching results...