Submission #1255825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255825		nerrrmin	Split the Attractions (IOI19_split)	C++20	18 / 100	55 ms	20168 KiB

split

#include "split.h"
#define pb push_back
using namespace std;
const int maxn = 3e5 + 10;
int m, deg[maxn];

vector < int > g[maxn];
int used[maxn];
vector < int > path;
void dfs(int beg, int from)
{
    used[beg] = 1;
    path.pb(beg);
    for (auto nb: g[beg])
    {
        if(used[nb])continue;
        dfs(nb, beg);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    m = p.size();
    for (int i = 0; i < m; ++ i)
    {
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
        deg[p[i]] ++;
        deg[q[i]] ++;
    }
    int start = 1;
    for (int i = 0; i < n; ++ i)
    {
        if(deg[i] == 1)
        {
            start = i;
            break;
        }
    }
    dfs(start, 0);
    for (int i = 0; i < a; ++ i)
        used[path[i]] = 1;
    for (int i = a; i < a+b; ++ i)
        used[path[i]] = 2;
    for (int i = a+b; i < n; ++ i)
        used[path[i]] = 3;

    vector < int > res;
    for (int i = 0; i < n; ++ i)
        res.pb(used[i]);

	return res;
}

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