Submission #1021835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021835		nisanduu	Split the Attractions (IOI19_split)	C++14	7 / 100	42 ms	9816 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);
	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);
	bool f=1;
	for(auto el:adj){
	    if(el.size()>2){
	        f=0;
	        break;
	    }
	}
	if(f){
    	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);
    	        }
    	    }
    	}
	}
	else{
	
    	stack<int> ds;
    	ds.push(0);
    	vector<int> vis1(n+10);
    // 	while(!ds.empty()){
    // 	    int node = ds.top();
    // 	    vis1[node]=1;
    // 	    ds.pop();
    // 	    if(B>0){
    // 	        res[node]=2;
    // 	        B--;
    // 	    }else if(A>0){
    // 	        A--;
    // 	        res[node]=1;
    // 	    }else{
    // 	        res[node]=3;
    // 	    }
    // 	    for(auto el:adj[node]){
    // 	        if(!vis1[el]){
    // 	            ds.push(el);
    // 	        }
    // 	    }
    // 	}
      while(!ds.empty()){
    	    int node = ds.top();
    	    vis1[node]=1;
    	    ds.pop();
    	    res[node]=2;
    	    for(auto el:adj[node]){
    	        if(!vis1[el]){
    	            ds.push(el);
    	        }
    	    }
    	}
	}
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:6:8: warning: unused variable 'A' [-Wunused-variable]
    6 |     ll A=a,B=b,C=c;
      |        ^
split.cpp:6:12: warning: unused variable 'B' [-Wunused-variable]
    6 |     ll A=a,B=b,C=c;
      |            ^
split.cpp:6:16: warning: unused variable 'C' [-Wunused-variable]
    6 |     ll A=a,B=b,C=c;
      |                ^

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