Submission #1047600

#TimeUsernameProblemLanguageResultExecution timeMemory
1047600NotLinuxSplit the Attractions (IOI19_split)C++17
7 / 100
30 ms9184 KiB
#include <bits/stdc++.h> #include "split.h" using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() const int N = 1e5 + 7; vector < int > graph[N] , color; int cur_color = 1; int dfs1(int node , int sayac){ if(sayac == 0)return node; // cout << "dfs : " << node << " , " << cur_color << endl; color[node] = cur_color; int ret = -1; for(auto itr : graph[node]){ if(color[itr] == -1){ ret = dfs1(itr , sayac - 1); break; } } return ret; } int subt[N] , tin[N] , tout[N]; vector < int > tour; int dfs2(int node , int past){ subt[node] = 1; tour.push_back(node); tin[node] = sz(tour) - 1; for(auto itr : graph[node]){ if(subt[itr] == -1){ subt[node] += dfs2(itr , node); } } tout[node] = sz(tour) - 1; return subt[node]; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { color.assign(n , -1); for(int i = 0;i<sz(p);i++){ graph[p[i]].push_back(q[i]); graph[q[i]].push_back(p[i]); } bool bl = 1; for(int i = 0;i<n;i++){ bl &= sz(graph[i]) <= 2; } if(bl){ int root = 0; for(int i = 0;i<n;i++){ if(sz(graph[i]) == 1){ root = i; break; } } // cout << "root0 : " << root << endl; root = dfs1(root , a); cur_color++; // cout << "root1 : " << root << endl; root = dfs1(root , b); cur_color++; // cout << "root2 : " << root << endl; root = dfs1(root , c); } else{ memset(subt , -1 , sizeof(subt)); dfs2(0 , 0); int suf[n+1][3]; memset(suf , 0 , sizeof(suf)); for(int i = n-1;i>=0;i--){ suf[i][0] = suf[i+1][0] + (subt[tour[i]] == a); suf[i][1] = suf[i+1][1] + (subt[tour[i]] == b); suf[i][2] = suf[i+1][2] + (subt[tour[i]] == c); } int query[3] = {a , b, c}; vector < int > perm = {0 , 1 , 2}; // cout << "tour : ";for(auto itr : tour)cout << itr << " ";cout << endl; do{ // cout << "colors : ";for(auto itr : perm)cout << itr << " ";cout << endl; int fa = query[perm[0]] , fb = query[perm[1]]; for(int i = 0;i<n;i++){ if(subt[tour[i]] == fa and suf[tout[tour[i]]+1][perm[1]] > 0){ color.assign(n , perm[2] + 1); // cout << "root for " << perm[0] + 1 << " : " << tour[i] << endl; for(int j = tin[tour[i]];j<=tout[tour[i]];j++){ color[tour[j]] = perm[0] + 1; } int root = -1; for(int j = tout[tour[i]] + 1;j<n;j++){ if(subt[tour[j]] == fb){ root = tour[j]; break; } } // cout << "root for " << perm[1] + 1 << " : " << root << endl; for(int j = tin[root];j<=tout[root];j++){ color[tour[j]] = perm[1] + 1; } return color; } } } while(next_permutation(all(perm))); color.assign(n , 0); } 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...