Submission #832865

#	Time	Username	Problem	Language	Result	Execution time	Memory
832865		HorizonWest	Split the Attractions (IOI19_split)	C++17	18 / 100	59 ms	14724 KiB

split

#include <bits/stdc++.h>
using namespace std;

vector <vector<int>> v;
vector <int> g, p1, ans, pass;

int last(int node)
{
    p1[node] = 1;
    for(auto& u : v[node])
        if(!p1[node]) return last(u);
    return node;
}

void dfs(int node, int& cont, int& group)
{
    ans[node] = group; cont++;
    if(cont == g[group])
    {
        cont = 0;
        group = max(1, (group + 1) % 4);
    }
    pass[node] = 1;
    for(auto& u : v[node])
    {
        if(!pass[u])
        {
            dfs(u, cont, group);
        }
    }

    return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    int m = p.size(); ans.assign(n, 3); pass.assign(n, 0);

    v.assign(n + 1, vector <int> ());
    vector <bool> subtask(5, 1);

    for(int i = 0; i < m; i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);

        if(v[p[i]].size() > 2) subtask[0] = false;
        if(v[q[i]].size() > 2) subtask[0] = false;
    }

    //if(subtask[0])
    //{
        p1.assign(n, 0); g.assign(4, 0);
        g[1] = a; g[2] = b; g[3] = c;
        int cont = 0, group = 2;
        dfs(last(0), cont, group);
        return ans;
    //}

	return ans;
}

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