oj.uz

Submission #143572

# Submission time Handle Problem Language Result Execution time Memory
143572 2019-08-14T16:01:11 Z VladaMG98 Split the Attractions (IOI19_split) C++17
22 / 100
 1008 ms 1048580 KB 
#include <bits/stdc++.h>
#include "split.h"
using namespace std;

const int MAXN = 100010;
int subtree_size[MAXN];
vector<int> adj[MAXN];

void dfs(int src = 0, int prev = -1) {
    //printf("dfs %d %d\n", src, prev);
    subtree_size[src] = 1;
    for(auto &xt : adj[src]) {
        if(xt - prev) {
            dfs(xt, src);
            subtree_size[src] += subtree_size[xt];
        }
    }
}

vector<int> get_solution(vector<int> v1, int n1, vector<int> v2, int n2, int n) {
    vector<int> ans(n, 6 - n1 - n2);
    for(auto &x : v1) {
        ans[x] = n1;
    }
    for(auto &x : v2) {
        ans[x] = n2;
    }
    return ans;
}

bool marked[MAXN];
vector<int> extract(int src, int wrong, int sz) {
    for(int i = 0; i < MAXN; i++) {
        marked[i] = false;
    }
    marked[wrong] = true;
    vector<int> ans;
    stack<int> nodes;
    nodes.push(src);
    marked[src] = true;
    while((int)ans.size() < sz) {
        int node = nodes.top();
        nodes.pop();
        ans.push_back(node);
        for(auto &x : adj[node]) {
            if(!marked[x]) {
                marked[x] = true;
                nodes.push(x);
            }
        }
    }
    return ans;
}

vector<int> blank(int n) {
    vector<int> ans(n, 0);
    return ans;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    pair<int, int> arr[] = {{a, 1}, {b, 2}, {c, 3}};
    sort(arr, arr + 3);
    int A = arr[0].first, B = arr[1].first, C = arr[2].first;
    int m = (int)p.size();
    for(int i = 0; i < m; i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    dfs();
    //for(int i = 0; i < n; i++) {
    //   printf("subtree_size[%d] = %d\n", i, subtree_size[i]);
    //}
    for(int i = 0; i < m; i++) {
        int u = p[i], v = q[i];
        if(subtree_size[u] > subtree_size[v]) swap(u, v);
        int under = subtree_size[u];
        int rest = n - under;
        if(under >= A && rest >= A) {
            //printf("found for edge %d - %d\n", u, v);
            //we've got a solution
            vector<int> set_A, set_B;
            if(under < rest) {
                set_A = extract(u, v, A);
                set_B = extract(v, u, B);
            } else {
                set_A = extract(v, u, A);
                set_B = extract(u, v, B);
            }
            return get_solution(set_A, arr[0].second, set_B, arr[1].second, n);
        }
    }
    //there is no edge connecting two subtrees of sizes >= a
    //meaning that it's a star with all subtrees attached of size < a
    //in tree, there is no such solution
    return blank(n);
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:63:45: warning: unused variable 'C' [-Wunused-variable]
     int A = arr[0].first, B = arr[1].first, C = arr[2].first;
                                             ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Runtime error 987 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2780 KB ok, correct split
2 Runtime error 1008 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Correct 82 ms 8820 KB ok, correct split
3 Correct 30 ms 4984 KB ok, correct split
4 Correct 4 ms 2808 KB ok, correct split
5 Correct 91 ms 10308 KB ok, correct split
6 Correct 106 ms 10144 KB ok, correct split
7 Correct 100 ms 10116 KB ok, correct split
8 Correct 98 ms 10840 KB ok, correct split
9 Correct 100 ms 9972 KB ok, correct split
10 Correct 27 ms 4472 KB ok, no valid answer
11 Correct 37 ms 5492 KB ok, no valid answer
12 Correct 74 ms 8460 KB ok, no valid answer
13 Correct 76 ms 8248 KB ok, no valid answer
14 Correct 80 ms 8496 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 985 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Runtime error 987 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -