Submission #397923

#	Time	Username	Problem	Language	Result	Execution time	Memory
397923		snasibov05	Split the Attractions (IOI19_split)	C++14	18 / 100	110 ms	14824 KiB

split

#include "split.h"

#define pb push_back

using namespace std;

const int nmax = 1e5 + 5;
vector<int> ed[nmax];
bool visited[nmax];
vector<int> ans;

int cur_a = 0, cur_b = 0, cur_c = 0;

void dfs(int v, int a, int b, int c){
    if (cur_a != a) ans[v] = 1, cur_a++;
    else if (cur_b != b) ans[v] = 2, cur_b++;
    else ans[v] = 3, cur_c++;
    
    visited[v] = true;
    
    for (auto to : ed[v]){
        if (!visited[to]) dfs(to, a, b, c);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {

    ans.resize(n);
    vector<int> deg(n);

    int m = p.size();
    for (int i = 0; i < m; ++i) {
        ed[p[i]].pb(q[i]);
        ed[q[i]].pb(p[i]);

        deg[p[i]]++;
        deg[q[i]]++;
    }

    int mni = 0;
    for (int i = 1; i < n; ++i) {
        if (deg[i] < deg[mni]) mni = i;
    }

    dfs(mni, a, b, c);
    
    return ans;

}

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