Submission #405677

#	Time	Username	Problem	Language	Result	Execution time	Memory
405677		Tc14	Split the Attractions (IOI19_split)	C++17	11 / 100	112 ms	12276 KiB

split

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

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

    int m;
    pii x, y, z;
    ve<ve<int>> G;
    ve<int> Ans;
    queue<int> Q;

    m = (int)p.size();
    G = ve<ve<int>>(n);

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

    ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
    sort(A.begin(), A.end());
    x = A[0];
    y = A[1];
    z = A[2];

    Ans = ve<int>(n, z.second);

    Q.push(0);
    Ans[0] = y.second;
    y.first--;

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : G[u]) {
            if (Ans[v] != y.second) {
                if (y.first > 0) {
                    Q.push(v);
                    Ans[v] = y.second;
                    y.first--;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (Ans[i] == z.second) {
            Ans[i] = x.second;
            break;
        }
    }

	return Ans;
}

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