Submission #1110754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110754		epicci23	Split the Attractions (IOI19_split)	C++17	18 / 100	68 ms	14972 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];
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);
}

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);
 }
  
 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: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36