Submission #1048042

#TimeUsernameProblemLanguageResultExecution timeMemory
1048042NotLinuxSplit the Attractions (IOI19_split)C++17
0 / 100
2066 ms20312 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)(x.size()) #define all(x) x.begin(), x.end() const int inf = 1e9 + 7; const int LIM1 = 1e5 + 7; int subt[LIM1] , N , A , B , C , vis[LIM1] , past[LIM1]; vector < int > graph[LIM1] , color , tree[LIM1]; int root = -1; pair < int , int > pai; random_device rd; mt19937 rng(rd()); // shuffle(v.begin() , v.end() , rng); int rand(int l, int r) { return rng() % (r - l + 1) + l; } void dfs(int node , int par){ // cout << "bruh0" << endl; subt[node] = 1; // cout << "bruh0.1" << endl; past[node] = par; // cout << "bruh0.2" << endl; if(par != -1)tree[par].push_back(node); // cout << "bruh0.3" << endl; shuffle(all(graph[node]) , rng); // cout << "bruh1" << endl; for(auto itr : graph[node]){ if(subt[itr] == -1){ dfs(itr , node); subt[node] += subt[itr]; } } // cout << node << " : " << subt[node] << " , " << par << endl; // if(node == 4)cout << "wtf : " << subt[node] << " >= " << C << " , " << N - subt[node] << " >= " << B << endl; if(subt[node] >= A and (N - subt[node]) >= B)pai = {1 , 2} , root = node; if(subt[node] >= B and (N - subt[node]) >= A)pai = {2 , 1} , root = node; if(subt[node] >= A and (N - subt[node]) >= C)pai = {1 , 3} , root = node; if(subt[node] >= C and (N - subt[node]) >= A)pai = {3 , 1} , root = node; if(subt[node] >= B and (N - subt[node]) >= C)pai = {2 , 3} , root = node; if(subt[node] >= C and (N - subt[node]) >= B)pai = {3 , 2} , root = node; } int sayac; void dfs1(int node , int paint){ if(sayac == 0)return; color[node] = paint; vis[node] = 1; sayac--; // cout << "Dfs : " << node << " , " << paint << " , " << past[node] << endl; for(auto itr : tree[node]){ if(vis[itr] == 0 and itr != past[node]){ // cout << node << "->" << itr << endl; dfs1(itr , paint); } } } void solve(){ root = -1; // cout << "flag-0"<<endl; memset(vis , 0 , sizeof(vis)); memset(subt , -1 , sizeof(subt)); for(int i = 0;i<LIM1;i++)tree[i].clear(); // cout << "flag-1"<<endl; dfs(0 , -1); // cout << "flag-2"<<endl; // cout << "root : "<< root << endl; // cout << "lower : " << pai.first << endl; // cout << "upper : " << pai.second << endl; if(root != -1){ int q[3] = {A , B , C}; set < int > ste = {1 , 2 , 3}; ste.erase(ste.find(pai.first)); ste.erase(ste.find(pai.second)); color.assign(N , *ste.begin()); // cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl; sayac = q[pai.first - 1]; dfs1(root , pai.first); // cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl; sayac = q[pai.second - 1]; dfs1(0 , pai.second); // cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl; } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { N = n , A = a , B = b , C = c; for(int i = 0;i<sz(p);i++){ graph[p[i]].push_back(q[i]); graph[q[i]].push_back(p[i]); } const int BRUH = 5000; color.assign(N , 0); // cout << "flag0" << endl; for(int i = 0;i<BRUH;i++){ // cout << "flag0.1" << endl; solve(); } // cout << "flag1" << endl; return color; }
#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...