Submission #1021879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021879		nisanduu	Split the Attractions (IOI19_split)	C++14	18 / 100	71 ms	13136 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) {
    ll A=a,B=b,C=c;
	vector<int> res(n);
	int m = p.size();
	vector<vector<int>> adj(n+2);
	for(int i=0;i<m;i++){
	    adj[p[i]].push_back(q[i]);
	    adj[q[i]].push_back(p[i]);
	}
	vector<int> vis(n+2);

	
    bool f1=0;
    if(B>C){
        swap(B,C);
        f1=1;
    }
    stack<int> ds;
    ds.push(0);
    vector<int> vis1(n+10);
    while(!ds.empty()){
        int node = ds.top();
        ds.pop();
        if(vis1[node]) continue;
        vis1[node]=1;
        if(B>0){
            res[node]=f1 ? 3 : 2;
            B--;
        }else if(A>0){
            A--;
            res[node]=1;
        }else{
            C--;
            res[node]=f1 ? 2 : 3;
        }
        for(auto el:adj[node]){
            if(!vis1[el]){
                ds.push(el);
            }
        }
    }
	assert(A==0&&B==0&&C==0);
	return res;
}

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