Submission #250045

#	Time	Username	Problem	Language	Result	Execution time	Memory
250045		DavidDamian	Split the Attractions (IOI19_split)	C++14	18 / 100	103 ms	13048 KiB

split

//#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> answer;
vector<int> adjList[100005];
int color[100005];
int cnt;
int A,B,C;
void dfs(int u)
{
    color[u]=1;
    answer[u]=2;
    cnt++;
    for(int v: adjList[u]){
        if(cnt<B){
            if(color[v]==0) dfs(v);
        }
    }
}
void dfs1(int u)
{
    color[u]=1;
    if(A){
        answer[u]=1;
        A--;
    }
    else if(B){
        answer[u]=2;
        B--;
    }
    else{
        answer[u]=3;
        C--;
    }
    for(int v: adjList[u]){
        if(color[v]==0)
            dfs1(v);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m=p.size();
	answer.resize(n);
	A=a,B=b,C=c;
	for(int i=0;i<m;i++){
        adjList[ p[i] ].push_back(q[i]);
        adjList[ q[i] ].push_back(p[i]);
	}
	if(a==1){
        dfs(0);
        for(int i=0;i<n;i++){
            if(answer[i]==0){
                if(a){
                    a--;
                    answer[i]=1;
                }
                else answer[i]=3;
            }
        }
	}
	else{
        int root=0;
        for(int i=0;i<n;i++){
            if(adjList[i].size()==1){
                root=i;
                break;
            }
        }
        dfs1(root);
	}
	return answer;
}

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