Submission #1110758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110758		epicci23	Split the Attractions (IOI19_split)	C++17	40 / 100	58 ms	17440 KiB

split

#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)x.size()

const int N = 1e5 + 5;
vector<int> v[N];
int vis[N],par[N],sub[N],cn;
vector<int> ans,comp;

void dfs(int c){
  if(vis[c]) return;
  vis[c]=1;
  comp.push_back(c);
  for(int x:v[c]) dfs(x);
}

void calc_sub(int c,int _p){
  sub[c]=1;
  par[c]=_p;
  for(int x:v[c]){
    if(x==_p) continue;
    calc_sub(x,c);
    sub[c]+=sub[x];
  }
}

void set_ans(int c,int col,int need){
  if(cn==need || vis[c]) return;
  ans[c]=col;
  vis[c]=1;
  cn++;
  for(int x:v[c]){
    if(x==par[c] || vis[x]) continue;
    set_ans(x,col,need);
  }
}


vector<int> find_split(int _n,int A,int B,int C,vector<int> u,vector<int> w){
 int n=_n,m=sz(u);
 ans.assign(n,0);
 vector<array<int,2>> s;
 s.push_back({A,1});
 s.push_back({B,2});
 s.push_back({C,3});
 sort(all(s));  
  
 for(int i=0;i<m;i++){
  int a=u[i],b=w[i];
  v[a].push_back(b);
  v[b].push_back(a);
 }

if(m==n-1){
  calc_sub(0,-1);
  for(int i=1;i<n;i++){
    if(sub[i]>=s[0][0] && sub[0]-sub[i]>=s[1][0]){
      cn=0;
      set_ans(i,s[0][1],s[0][0]);
      cn=0;
      set_ans(0,s[1][1],s[1][0]);
      for(int j=0;j<n;j++) if(!ans[j]) ans[j]=s[2][1];
      break;
    }
    if(sub[i]>=s[1][0] && sub[0]-sub[i]>=s[0][0]){
      cn=0;
      set_ans(i,s[1][1],s[1][0]);
      cn=0;
      set_ans(0,s[0][1],s[0][0]);
      for(int j=0;j<n;j++) if(!ans[j]) ans[j]=s[2][1];
      break;
    }
  }
  return ans;
}

  
 int p=1;

  for(int i=0;i<n;i++){
  	if(p<0) break;
  	comp.clear();
  	dfs(i);
  	for(int j=0;j<2;j++){
  	 if(p<0) break;
     if(sz(comp)>=s[p][0]){
      for(int z=0;z<s[p][0];z++){
      	ans[comp.back()]=s[p][1];
      	comp.pop_back();
      }
      p--;
     }
    }
  }

  for(int i=0;i<n;i++) if(ans[i]==0) ans[i] = s[2][1]; 
  return ans;
}


/*void _(){
  int n,m;
  cin >> n >> m;
  vector<array<int,2>> s;
  for(int i=1;i<=3;i++){
  	int a; cin >> a;
  	s.push_back({a,i});
  }
  sort(all(s));
  
  for(int i=1;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].push_back(b);
  	v[b].push_back(a);
  }
  
  int p = 1;

  for(int i=0;i<n;i++){
  	if(p<0) break;
  	comp.clear();
  	dfs(i);
  	for(int j=0;j<2;j++){
  	 if(p<0) break;
     if(sz(comp)>=s[p][0]){
      for(int z=0;z<s[p][0];z++){
      	ans[comp.back()]=s[p][1];
      	comp.pop_back();
      }
      p--;
     }
    }
  }
  for(int i=0;i<n;i++) if(ans[i]==0) ans[i] = s[2][1];
}

int32_t main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
}*/

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36