oj.uz

Submission #971903

# Submission time Handle Problem Language Result Execution time Memory
971903 2024-04-29T13:01:28 Z opPO Split the Attractions (IOI19_split) C++14
18 / 100
 59 ms 18256 KB 
#include "split.h"
#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()

using namespace std;

void dfs(int v, vector<vector<int>> &g, vector<bool> &used, vector<int> &vec, int need) {
    if (sz(vec) >= need) return;
    if (used[v]) return;
    used[v] = 1;
    vec.push_back(v);
    for (int &u : g[v]) {
        if (used[u]) continue;
        dfs(u, g, used, vec, need);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = sz(p);
	vector<int> res(n);

	vector<int> deg(n);
	vector<vector<int>> g(n);
	for (int i = 0; i < m; i++) {
        deg[p[i]]++;
        deg[q[i]]++;
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
	}
	int vert = 0;
	for (int i = 0; i < n; i++) {
        if (deg[i] < deg[vert]) {
            vert = i;
        }
	}

	vector<int> v = {0, a, b, c};
	vector<int> perm = {1, 2, 3};
	sort(all(perm), [&](int i, int j){
        return v[i] < v[j];
    });

    vector<bool> used(n);
    vector<int> A;
    dfs(vert, g, used, A, v[perm[0]]);
    assert(sz(A) == v[perm[0]]);
    for (int &i : A) {
        res[i] = perm[0];
    }

    int unused = -1;
    for (int v = 0; v < n; v++) {
        if (!used[v]) {
            unused = v;
        }
    }
    assert(unused != -1);
    vector<int> B;
    dfs(unused, g, used, B, v[perm[1]]);
    assert(sz(B) == v[perm[1]]);
    for (int &i : B) {
        res[i] = perm[1];
    }

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            res[i] = perm[2];
        }
    }

	return res;
}

/*
9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
*/

/*
g++ -std=gnu++14 -O2 -Wall -pipe -static -o "split" "grader.cpp" "split.cpp"
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 40 ms 12352 KB ok, correct split
8 Correct 35 ms 9268 KB ok, correct split
9 Correct 39 ms 13412 KB ok, correct split
10 Correct 34 ms 9308 KB ok, correct split
11 Correct 39 ms 12352 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 48 ms 11092 KB ok, correct split
5 Correct 38 ms 9796 KB ok, correct split
6 Correct 36 ms 9300 KB ok, correct split
7 Correct 38 ms 13524 KB ok, correct split
8 Correct 59 ms 13148 KB ok, correct split
9 Correct 39 ms 9820 KB ok, correct split
10 Correct 35 ms 9972 KB ok, correct split
11 Correct 32 ms 9784 KB ok, correct split
12 Correct 33 ms 10188 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Runtime error 31 ms 18256 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 40 ms 12352 KB ok, correct split
8 Correct 35 ms 9268 KB ok, correct split
9 Correct 39 ms 13412 KB ok, correct split
10 Correct 34 ms 9308 KB ok, correct split
11 Correct 39 ms 12352 KB ok, correct split
12 Correct 0 ms 348 KB ok, correct split
13 Correct 0 ms 348 KB ok, correct split
14 Correct 1 ms 348 KB ok, correct split
15 Correct 48 ms 11092 KB ok, correct split
16 Correct 38 ms 9796 KB ok, correct split
17 Correct 36 ms 9300 KB ok, correct split
18 Correct 38 ms 13524 KB ok, correct split
19 Correct 59 ms 13148 KB ok, correct split
20 Correct 39 ms 9820 KB ok, correct split
21 Correct 35 ms 9972 KB ok, correct split
22 Correct 32 ms 9784 KB ok, correct split
23 Correct 33 ms 10188 KB ok, correct split
24 Correct 1 ms 344 KB ok, correct split
25 Runtime error 31 ms 18256 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -