Submission #717916

#	Time	Username	Problem	Language	Result	Execution time	Memory
717916		bebra	Split the Attractions (IOI19_split)	C++17	11 / 100	85 ms	12748 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 1e5 + 5;
vector<int> g[MAX_N];
bool used[MAX_N];
int color[MAX_N];


int cnt;

void dfs(int v) {

    if (cnt == 0) {
        return;
    }

    --cnt;
    used[v] = true;
    color[v] = 2;

    for (auto u : g[v]) {
        if (used[u]) continue;
        dfs(u);
    }
}


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) {
        int u = p[i];
        int v = q[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }

    cnt = b;
    fill_n(color, n, 3);

    dfs(0);
    for (int v = 0; v < n; ++v) {
        if (color[v] == 3) {
            color[v] = 1;
            break;
        }
    }


    vector<int> res(n);
    for (int i = 0; i < n; ++i) {
        res[i] = color[i];
    }

	return res;
}


// int main() {

//     int n, m;
//     cin >> n >> m;

//     int a, b, c;
//     cin >> a >> b >> c;

//     vector<int> p(m), q(m);
//     for (int i = 0; i < m; ++i) {
//         cin >> p[i] >> q[i];
//     }

//     for (auto x : find_split(n, a, b, c, p, q)) {
//         cout << x << ' ';
//     }
//     cout << '\n';

// }

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