Submission #1255821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255821		nerrrmin	Split the Attractions (IOI19_split)	C++20	11 / 100	50 ms	15816 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], lt;
void dfs(int beg, int from)
{
    if(!lt)return;
    used[beg] = 2;
    lt --;
    if(!lt)return;
    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]] ++;
    }
    lt = b;
    dfs(1, 0);
    for (int i = 0; i < n; ++ i)
    {
        if(!used[i])
        {
            used[i] = 1;
            break;
        }
    }
    for (int i = 0; i < n; ++ i)
        if(!used[i])used[i] = 3;
    vector < int > res;
    for (int i = 0; i < n; ++ i)
        res.pb(used[i]);

	return res;
}

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