Submission #1019976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019976		nisanduu	Split the Attractions (IOI19_split)	C++14	7 / 100	117 ms	16212 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res(n);
	int m = p.size();
	vector<vector<int>> adj(n+2);
	vector<int> calls(n+2);
	for(int i=0;i<m;i++){
	    adj[p[i]].push_back(q[i]);
	    adj[q[i]].push_back(p[i]);
	    calls[p[i]]++;
	    calls[q[i]]++;
	}
	vector<int> vis(n+2);
	int st = 0;
	for(int i=0;i<n;i++){
	    if(calls[i]==1){
	        st=i;
	        break;
	    }
	}
	queue<int> pq;
	pq.push(st);
	while(!pq.empty()){
	    int node = pq.front();
	    pq.pop();
	    vis[node]=1;
	    if(a>0){
	        res[node]=1;
	        a--;
	    }else if(b>0){
	        b--;
	        res[node]=2;
	    }else{
	        c--;
	        res[node]=3;
	    }
	    for(auto el:adj[node]){
	        if(!vis[el]){
	            pq.push(el);
	        }
	    }
	}
	return res;
}

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