Submission #1077722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077722		Ignut	Split the Attractions (IOI19_split)	C++17	18 / 100	55 ms	14704 KiB

split

// Ignut

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 123;
int n;
int a, b, c;
int colorA = 1, colorB = 2, colorC = 3;

vector<int> g[MAXN];
bool used[MAXN];

int vert = -1;

vector<int> res;

vector<int> order;

void dfs(int v) {
    used[v] = true;
    order.push_back(v);
    for (int to : g[v])
        if (!used[to])
            dfs(to);
}

vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
    int M = P.size();
    for (int i = 0; i < M; i ++) {
        g[P[i]].push_back(Q[i]);
        g[Q[i]].push_back(P[i]);
    }
    
    for (int i = 0; i < N; i ++) {
        if (used[i]) continue;
        if (g[i].size() != 1) continue;
        dfs(i);
    }
    for (int i = 0; i < N; i ++) {
        if (used[i]) continue;
        dfs(i);
    }

    res.assign(N, 3);
    for (int i = 0; i < A; i ++)
        res[order[i]] = 1;
    for (int i = A; i < A + B; i ++)
        res[order[i]] = 2;

    return res;
}

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