제출 #987213

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

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2500;

vector <int> g[N];
vector <int> tipos = {1, 2, 3};
int pai[N];
int sz[N];
int mark[N];
int n;
void dfs(int v, int p){
	mark[v] = 1;
	sz[v] = 1;
	pai[v] = p;
	for(auto x : g[v]){
		if(mark[x]) continue;
		dfs(x, v);
		sz[v] += sz[x];
	}
	return;
}

vector <int> ar[N];
int res[N];

void dfs2(int v, int p, int &tam, int typ){
	if(tam == 0) return;
	res[v] = typ;
	tam--;
	for(auto x : ar[v]){
		if(x == p) continue;
		dfs2(x,v,tam,typ);
	}
	return;
}

void solve(int v, int a, int b){
	for(int i = 1;i <= n;i++){
		if(pai[i] == i) continue;
		ar[i].push_back(pai[i]);
		ar[pai[i]].push_back(i);
	}
	dfs2(v, pai[v], a, tipos[0]);
	dfs2(pai[v], v, b, tipos[1]);
	for(int i = 1;i <= n;i++) if(res[i] == 0) res[i] = tipos[2];
	return;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	for(int i = 0;i < p.size();i++){
		int x = p[i]+1, y = q[i]+1;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	if(a > b){
		swap(a, b);
		swap(tipos[0], tipos[1]);
	}
	if(a > c){
		swap(a, c);
		swap(tipos[0], tipos[2]);
	}
	if(b > c){
		swap(b, c);
		swap(tipos[1], tipos[2]);
	}
	for(int st = 1;st <= n;st++){
		memset(mark, 0, sizeof mark);
		dfs(st, st);
		for(int i = 1;i <= n;i++){
			if(sz[i] >= b and n-sz[i] >= a){
				swap(a, b);
				swap(tipos[0], tipos[1]);
			}
			if(sz[i] >= a and n-sz[i] >= b){
				solve(i, a, b);
				vector <int> ans;
				for(int i = 1;i <= n;i++) ans.push_back(res[i]);
				return ans;
			}
		}
	}
	vector <int> ans;
	for(int i = 0;i < n;i++) ans.push_back(0);
	return ans;
}

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0;i < p.size();i++){
      |                ~~^~~~~~~~~~

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