oj.uz

Submission #143465

# Submission time Handle Problem Language Result Execution time Memory
143465 2019-08-14T07:02:06 Z icypiggy Split the Attractions (IOI19_split) C++14
40 / 100
 167 ms 27928 KB 
#include <bits/stdc++.h>
using namespace std;
const int n_max = 2e5+1e3;
int visit[n_max];
int low[n_max];
int subtree[n_max];
vector<int> adj[n_max];
vector<int> child[n_max];
int parent[n_max];
int time_global = 0;
void dfs(int x) {
    subtree[x] = 1;
    visit[x] = time_global;
    time_global++;
    low[x] = visit[x];
    for(int i: adj[x]) {
        if(visit[i]==-1) {
            parent[i] = x;
            child[x].push_back(i);
            dfs(i);
            subtree[x] += subtree[i];
            low[x] = min(low[x], low[i]);
        } else if (i != parent[x]) {
            low[x] = min(low[x], visit[i]);
        }
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    // assume a<=b<=c
    vector<pair<int,int>> vp = {make_pair(a,1),make_pair(b,2),make_pair(c,3)};
    sort(vp.begin(), vp.end());
    int small = vp[0].second;
    int mid = vp[1].second;
    int big = vp[2].second;
    a = vp[0].first;
    b = vp[1].first;
    c = vp[2].first;

    memset(visit, -1, sizeof(visit));
    for(int i=0; i<(int) p.size(); i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    dfs(0);
    vector<int> ans(n,0);
    for(int i=0; i<n; i++) {
        // assume c>=a
        // check: a+c or b+c?
        if(subtree[i]>=a && subtree[i]<=b+c) {
            if(subtree[i]>a+c) {
                swap(a,b);
                swap(small,mid);
            }
            queue<int> bfs;
            bfs.push(i);
            int ctr = 0;
            while(!bfs.empty()) {
                int next = bfs.front();
                ans[next] = (ctr<a ? small : big);
                ctr++;
                bfs.pop();
                for(int k: child[next]) {
                    bfs.push(k);
                }
            }
            bfs.push(0);
            ctr = 0;
            while(!bfs.empty()) {
                int next = bfs.front();
                ans[next] = (ctr<b ? mid : big);
                ctr++;
                bfs.pop();
                for(int k: child[next]) {
                    if(ans[k]==0) {
                        bfs.push(k);
                    }
                }
            }
            for(int k=0; k<n; k++) {
                assert(ans[k]!=0);
            }
            return ans;
        } else if(subtree[i]>b+c) {
            // if have heavy node with all light children
            bool all_light = true;
            for(int j: child[i]) {
                if(subtree[j]>=a) {
                    all_light = false;
                    // break;
                }
            }
            if(all_light) {
              return ans;
                if(i==0) {
                    assert(child[i].size()>=3);
                    return ans;
                }
                int minsize = 1;
                vector<int> tmp; // consists of all the children to be taken
                for(int j: child[i]) {
                    // add all those with bad lowtime
                    if(low[j]>= visit[i]) {
                        minsize += subtree[j];
                        tmp.push_back(j);
                    }
                }
                if(minsize > b+c) {
                    return ans;
                }
                for(int j: child[i]) {
                    // add the relevant subtrees
                    if(low[j]<visit[i] && minsize < b) {
                        minsize += subtree[j];
                        tmp.push_back(j);
                    }
                }
                assert(minsize >= b);
                assert(minsize <= b+c);
                // now for each subtree, color its children completely except that some are colored with 3
                int ctr = 1;
                ans[i] = mid;
                queue<int> bfs;
                for(int j: tmp) {
                    bfs.push(j);
                    while(!bfs.empty()) {
                        int next = bfs.front();
                        assert(ans[next]==0);
                        ans[next] = (ctr<b ? mid : big);
                        ctr++;
                        bfs.pop();
                        for(int k: child[next]) {
                            bfs.push(k);
                        }
                    }
                }
                //assert(ctr==b);
                ctr = 1;
                bfs.push(0); // we know that 0 is not the root
                ans[0] = small;
                while(!bfs.empty()) {
                    int next = bfs.front();
                    bfs.pop();
                    for(int k: adj[next]) {
                        if(ans[k]==0) {
                            bfs.push(k);
                            ans[k] = (ctr<a ? small : big);
                            ctr++;
                        }
                    }
                }
                //assert(ctr==a);
                for(int k=0; k<n; k++) {
                    //assert(ans[k]!=0);
                }
                return ans;
            }
        }
    }
    assert(false);
    return p;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10616 KB ok, correct split
2 Correct 11 ms 10616 KB ok, correct split
3 Correct 11 ms 10616 KB ok, correct split
4 Correct 11 ms 10616 KB ok, correct split
5 Correct 11 ms 10616 KB ok, correct split
6 Correct 11 ms 10616 KB ok, correct split
7 Correct 142 ms 27384 KB ok, correct split
8 Correct 140 ms 25208 KB ok, correct split
9 Correct 136 ms 24440 KB ok, correct split
10 Correct 142 ms 27928 KB ok, correct split
11 Correct 136 ms 27892 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10488 KB ok, correct split
2 Correct 14 ms 10616 KB ok, correct split
3 Correct 13 ms 10616 KB ok, correct split
4 Correct 167 ms 23648 KB ok, correct split
5 Correct 112 ms 18680 KB ok, correct split
6 Correct 141 ms 27768 KB ok, correct split
7 Correct 129 ms 24952 KB ok, correct split
8 Correct 158 ms 21216 KB ok, correct split
9 Correct 120 ms 20092 KB ok, correct split
10 Correct 76 ms 17996 KB ok, correct split
11 Correct 76 ms 18032 KB ok, correct split
12 Correct 94 ms 18032 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10616 KB ok, correct split
2 Correct 115 ms 18680 KB ok, correct split
3 Correct 45 ms 13816 KB ok, correct split
4 Correct 11 ms 10488 KB ok, correct split
5 Correct 127 ms 22624 KB ok, correct split
6 Correct 129 ms 22356 KB ok, correct split
7 Correct 133 ms 22372 KB ok, correct split
8 Correct 138 ms 23532 KB ok, correct split
9 Correct 131 ms 21880 KB ok, correct split
10 Correct 38 ms 13216 KB ok, no valid answer
11 Correct 53 ms 14584 KB ok, no valid answer
12 Correct 88 ms 18032 KB ok, no valid answer
13 Correct 108 ms 18424 KB ok, no valid answer
14 Correct 73 ms 17772 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10488 KB ok, correct split
2 Correct 11 ms 10616 KB ok, no valid answer
3 Correct 13 ms 10620 KB ok, correct split
4 Correct 11 ms 10616 KB ok, correct split
5 Correct 11 ms 10616 KB ok, correct split
6 Correct 11 ms 10488 KB ok, correct split
7 Correct 11 ms 10488 KB ok, correct split
8 Correct 11 ms 10616 KB ok, correct split
9 Correct 13 ms 10876 KB ok, correct split
10 Correct 13 ms 10744 KB ok, correct split
11 Correct 11 ms 10616 KB ok, correct split
12 Correct 13 ms 10872 KB ok, correct split
13 Correct 11 ms 10488 KB ok, correct split
14 Correct 11 ms 10616 KB ok, correct split
15 Correct 10 ms 10616 KB ok, correct split
16 Correct 11 ms 10616 KB ok, correct split
17 Correct 10 ms 10616 KB ok, correct split
18 Correct 11 ms 10488 KB ok, correct split
19 Correct 18 ms 10644 KB ok, correct split
20 Correct 15 ms 10716 KB ok, correct split
21 Correct 12 ms 10872 KB ok, correct split
22 Correct 13 ms 10780 KB ok, correct split
23 Correct 13 ms 10872 KB ok, correct split
24 Correct 11 ms 10872 KB ok, correct split
25 Correct 13 ms 10872 KB ok, correct split
26 Incorrect 14 ms 10872 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10616 KB ok, correct split
2 Correct 11 ms 10616 KB ok, correct split
3 Correct 11 ms 10616 KB ok, correct split
4 Correct 11 ms 10616 KB ok, correct split
5 Correct 11 ms 10616 KB ok, correct split
6 Correct 11 ms 10616 KB ok, correct split
7 Correct 142 ms 27384 KB ok, correct split
8 Correct 140 ms 25208 KB ok, correct split
9 Correct 136 ms 24440 KB ok, correct split
10 Correct 142 ms 27928 KB ok, correct split
11 Correct 136 ms 27892 KB ok, correct split
12 Correct 11 ms 10488 KB ok, correct split
13 Correct 14 ms 10616 KB ok, correct split
14 Correct 13 ms 10616 KB ok, correct split
15 Correct 167 ms 23648 KB ok, correct split
16 Correct 112 ms 18680 KB ok, correct split
17 Correct 141 ms 27768 KB ok, correct split
18 Correct 129 ms 24952 KB ok, correct split
19 Correct 158 ms 21216 KB ok, correct split
20 Correct 120 ms 20092 KB ok, correct split
21 Correct 76 ms 17996 KB ok, correct split
22 Correct 76 ms 18032 KB ok, correct split
23 Correct 94 ms 18032 KB ok, correct split
24 Correct 11 ms 10616 KB ok, correct split
25 Correct 115 ms 18680 KB ok, correct split
26 Correct 45 ms 13816 KB ok, correct split
27 Correct 11 ms 10488 KB ok, correct split
28 Correct 127 ms 22624 KB ok, correct split
29 Correct 129 ms 22356 KB ok, correct split
30 Correct 133 ms 22372 KB ok, correct split
31 Correct 138 ms 23532 KB ok, correct split
32 Correct 131 ms 21880 KB ok, correct split
33 Correct 38 ms 13216 KB ok, no valid answer
34 Correct 53 ms 14584 KB ok, no valid answer
35 Correct 88 ms 18032 KB ok, no valid answer
36 Correct 108 ms 18424 KB ok, no valid answer
37 Correct 73 ms 17772 KB ok, no valid answer
38 Correct 11 ms 10488 KB ok, correct split
39 Correct 11 ms 10616 KB ok, no valid answer
40 Correct 13 ms 10620 KB ok, correct split
41 Correct 11 ms 10616 KB ok, correct split
42 Correct 11 ms 10616 KB ok, correct split
43 Correct 11 ms 10488 KB ok, correct split
44 Correct 11 ms 10488 KB ok, correct split
45 Correct 11 ms 10616 KB ok, correct split
46 Correct 13 ms 10876 KB ok, correct split
47 Correct 13 ms 10744 KB ok, correct split
48 Correct 11 ms 10616 KB ok, correct split
49 Correct 13 ms 10872 KB ok, correct split
50 Correct 11 ms 10488 KB ok, correct split
51 Correct 11 ms 10616 KB ok, correct split
52 Correct 10 ms 10616 KB ok, correct split
53 Correct 11 ms 10616 KB ok, correct split
54 Correct 10 ms 10616 KB ok, correct split
55 Correct 11 ms 10488 KB ok, correct split
56 Correct 18 ms 10644 KB ok, correct split
57 Correct 15 ms 10716 KB ok, correct split
58 Correct 12 ms 10872 KB ok, correct split
59 Correct 13 ms 10780 KB ok, correct split
60 Correct 13 ms 10872 KB ok, correct split
61 Correct 11 ms 10872 KB ok, correct split
62 Correct 13 ms 10872 KB ok, correct split
63 Incorrect 14 ms 10872 KB jury found a solution, contestant did not
64 Halted 0 ms 0 KB -