제출 #1045418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045418		vjudge1	Split the Attractions (IOI19_split)	C++17	40 / 100	55 ms	23888 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(0);
vector<int>adj[100100],adj2[100100];
bitset<100100>vis;
int sz[100100],THEONE;
vector<int>ans;
int OK(int k,int a,int b,int c){
	sz[k]=1;
	vis[k]=1;
	for(auto i:adj[k]) if(!vis[i]){
		if(OK(i,a,b,c)) return 1;
		sz[k]+=sz[i];
	}
	if(a<=sz[k]&&sz[k]<=b+c)
		return THEONE=k,1;
	return 0;
}
void gendfstree(int n){
	vis[n]=1;
	for(auto i:adj[n])
		if(!vis[i]) gendfstree(i),
		adj2[n].push_back(i),
		adj2[i].push_back(n);
}
void docol(int n,int p,int &CC,int col){
	if(!CC) return;
	ans[n]=col,CC--;
	for(auto x:adj2[n])
		if(x-p)docol(x,n,CC,col);
}
void genans(int k,int a,int b,int c,int A,int B,int C){
	for(auto&i:ans)i=C;
	vis.reset();
	gendfstree(k);
	int n=a+b+c;
	if(sz[THEONE]>=b)
		swap(a,b),swap(A,B);
	docol(THEONE,adj2[THEONE].back(),a,A);
	docol(adj2[THEONE].back(),THEONE,b,B);
	assert(!a&&!b);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	ans.resize(n);
	vector<int> res;
    int K=clock();
	int m=p.size();
	for(int i=0;i<m;i++)
		adj[p[i]].push_back(q[i]),
		adj[q[i]].push_back(p[i]);
	int A=1,B=2,C=3;
	if(a>b)swap(a,b),swap(A,B);
	if(b>c)swap(b,c),swap(B,C);
	if(a>b)swap(a,b),swap(A,B);
	vector<int>v(n);
	iota(v.begin(),v.end(),0);
	shuffle(v.begin(),v.end(),rng);
	for(auto i:v){
		vis.reset();
		if(OK(i,a,b,c)){
			genans(i,a,b,c,A,B,C);
			break;
		}
		if(clock()-K>1500)break;
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'void genans(int, int, int, int, int, int, int)':
split.cpp:37:6: warning: unused variable 'n' [-Wunused-variable]
   37 |  int n=a+b+c;
      |      ^

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