제출 #827030

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

split

#include<bits/stdc++.h>
#include "split.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ll long long
#define vout(v) for(int i=0; i<v.size(); i++) cout<<v[i]<<' '
#define pii pair<int, int>
#define ff first
#define ss second
#define mp make_pair
    
vector<int> q[200100];
int sz[200100];
int res[200100], p[200100];

void dfs1(int v){
	sz[v] = 1;
	for(int i=0; i<q[v].size(); i++){
		int to = q[v][i];
		if(to == p[v]) continue;
		p[to] = v;
		dfs1(to);
		sz[v] += sz[to];
	}	
}

int dfs2(int v, int x, int c){
	res[v] = c;
	//cout<<v<<'\n';
	x--;
	for(int i=0; i<q[v].size() and x != 0; i++){
		int to = q[v].size();
		if(p[v] == to) continue;
		p[to] = v;
		x = dfs2(to, x, c);
	}
	return x;
}

vector<int> find_split(int n, int A, int B, int C, vector<int> LL, vector<int> RR){
	int m = LL.size();
	for(int i=0; i<m; i++){
		q[LL[i] + 1].pb(RR[i] + 1);
		q[RR[i] + 1].pb(LL[i] + 1);
	}
	if(A == 1){
		p[1] = 0;
		dfs2(1, B, 2);
		vector<int> ans(n);
		for(int i=1; i<=n; i++){
			if(res[i] == 0){
				if(C){
					C--;
					res[i] = 3;
				}
				else{
					res[i] = 1;
				}
			}
			ans[i-1] = res[i];
		}
		return ans;

	}
	//cout<<"asdasdasdasd\n\n\n\n\n";
	if(n == m+1){
		p[1] = 0;
		dfs1(1);
		vector<pii> qq;
		qq.pb(mp(A, 1));
		qq.pb(mp(B, 2));
		qq.pb(mp(C, 3));
		sort(all(qq));
		pii d1=qq[0], d2=qq[1];
		int ok=0;
		for(int i=2; i<=n; i++){
			//cout<<sz[i];
			if(min(d1.ff, d2.ff) <= min(sz[i], n-sz[i]) and max(d1.ff, d2.ff) <= max(sz[i], n-sz[i])){
				ok=i;
				break;
			}
		}
		vector<int> ans(n, 0);
		//cout<<ok<<"\n\n\n\n";
		if(!ok){
			return ans;
		}
		if(sz[ok] > n - sz[ok]){
			dfs2(ok, d2.ff, d2.ss);
			p[p[ok]] = ok;
			dfs2(p[ok], d1.ff, d1.ss);
		}
		else{
			dfs2(ok, d1.ff, d1.ss);
			p[p[ok]] = ok;
			dfs2(p[ok], d2.ff, d2.ss);
		}
		for(int i=1; i<=n; i++){
			if(res[i] == 0) res[i] = qq[2].ss;
			ans[i-1] = res[i];
		}
		
		return ans;

	}
	vector<int> ans;
	for(int i=1; i<=A; i++){
		ans.pb(1);
	}
	for(int i=1; i<=B; i++){
		ans.pb(2);
	}

	for(int i=1; i<=C; i++){
		ans.pb(3);
	}


	return ans;
}




                 

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

split.cpp: In function 'void dfs1(int)':
split.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0; i<q[v].size(); i++){
      |               ~^~~~~~~~~~~~
split.cpp: In function 'int dfs2(int, int, int)':
split.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0; i<q[v].size() and x != 0; i++){
      |               ~^~~~~~~~~~~~

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