Submission #1229355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229355		Gray	Split the Attractions (IOI19_split)	C++20	7 / 100	41 ms	13896 KiB

split

#include "split.h"
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;

vector<vector<int>> A;
ll n;

void dfs(ll u, ll &cnt, ll wr, vector<int> &val){
    val[u]=wr; cnt--;
    if (cnt==0) return;
    for (auto v:A[u]){
        if (val[v]) continue;
        dfs(v, cnt, wr, val);
        if (cnt==0) return;
    }
}

vector<int> find_split(int N, int ca, int cb, int cc, vector<int> p, vector<int> q) {
    A.clear();
    n=N; A.resize(n);
    for (ll i=0; i<(ll)p.size(); i++){
        A[p[i]].push_back(q[i]);
        A[q[i]].push_back(p[i]);
    }
    vector<ll> ends;
    for (ll i=0; i<n; i++){
        if (A[i].size()==1) ends.push_back(i);
    }
    if(ends.empty()){
        vector<int> res(n);
        ll a=ca; dfs(0, a, 1, res);
        ll b=cb; for (ll i=0; i<n; i++){
            if (res[i]==0){
                dfs(i, b, 2, res);
                break;
            }
        }
        for (ll i=0; i<n; i++) if (res[i]==0) res[i]=3;
        return res;
    }else{
        vector<int> res(n);
        ll a=ca; dfs(ends[0], a, 1, res);
        ll b=cb; dfs(ends[1], b, 2, res);
        for (ll i=0; i<n; i++) if (res[i]==0) res[i]=3;
        return res;
    }
}

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