oj.uz

Submission #143459

# Submission time Handle Problem Language Result Execution time Memory
143459 2019-08-14T06:38:31 Z icypiggy Split the Attractions (IOI19_split) C++14
18 / 100
 212 ms 27896 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] = 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) {
                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 11 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 10488 KB ok, correct split
5 Correct 11 ms 10488 KB ok, correct split
6 Correct 14 ms 10488 KB ok, correct split
7 Correct 143 ms 27332 KB ok, correct split
8 Correct 138 ms 25080 KB ok, correct split
9 Correct 135 ms 24568 KB ok, correct split
10 Correct 144 ms 27896 KB ok, correct split
11 Correct 135 ms 27740 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 11 ms 10616 KB ok, correct split
3 Correct 11 ms 10616 KB ok, correct split
4 Correct 152 ms 23644 KB ok, correct split
5 Correct 108 ms 18552 KB ok, correct split
6 Correct 138 ms 27808 KB ok, correct split
7 Correct 134 ms 25008 KB ok, correct split
8 Correct 212 ms 21308 KB ok, correct split
9 Correct 119 ms 20216 KB ok, correct split
10 Correct 74 ms 18068 KB ok, correct split
11 Correct 71 ms 18028 KB ok, correct split
12 Correct 77 ms 18032 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10616 KB ok, correct split
2 Correct 111 ms 18692 KB ok, correct split
3 Correct 46 ms 13816 KB ok, correct split
4 Correct 11 ms 10616 KB ok, correct split
5 Correct 138 ms 22520 KB ok, correct split
6 Correct 153 ms 22380 KB ok, correct split
7 Correct 125 ms 22136 KB ok, correct split
8 Correct 130 ms 23408 KB ok, correct split
9 Correct 127 ms 21996 KB ok, correct split
10 Correct 38 ms 13176 KB ok, no valid answer
11 Correct 53 ms 14496 KB ok, no valid answer
12 Correct 89 ms 18548 KB ok, no valid answer
13 Incorrect 112 ms 18652 KB answer contains both zero and positive values
14 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10488 KB ok, correct split
2 Correct 11 ms 10488 KB ok, no valid answer
3 Correct 10 ms 10488 KB ok, correct split
4 Correct 10 ms 10488 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 10616 KB ok, correct split
8 Correct 11 ms 10616 KB ok, correct split
9 Correct 13 ms 10872 KB ok, correct split
10 Correct 13 ms 10872 KB ok, correct split
11 Correct 13 ms 10616 KB ok, correct split
12 Correct 13 ms 10876 KB ok, correct split
13 Correct 11 ms 10744 KB ok, correct split
14 Correct 11 ms 10616 KB ok, correct split
15 Correct 11 ms 10616 KB ok, correct split
16 Correct 11 ms 10616 KB ok, correct split
17 Correct 11 ms 10616 KB ok, correct split
18 Correct 11 ms 10488 KB ok, correct split
19 Correct 11 ms 10616 KB ok, correct split
20 Correct 11 ms 10744 KB ok, correct split
21 Correct 12 ms 10872 KB ok, correct split
22 Correct 13 ms 10872 KB ok, correct split
23 Correct 13 ms 10872 KB ok, correct split
24 Correct 13 ms 10872 KB ok, correct split
25 Correct 13 ms 10872 KB ok, correct split
26 Correct 13 ms 10876 KB ok, correct split
27 Correct 13 ms 10872 KB ok, correct split
28 Correct 13 ms 10744 KB ok, correct split
29 Correct 11 ms 10616 KB ok, correct split
30 Correct 13 ms 10744 KB ok, correct split
31 Correct 11 ms 10588 KB ok, correct split
32 Correct 11 ms 10616 KB ok, correct split
33 Correct 11 ms 10616 KB ok, correct split
34 Correct 13 ms 10744 KB ok, correct split
35 Correct 13 ms 10744 KB ok, correct split
36 Correct 12 ms 10744 KB ok, correct split
37 Correct 13 ms 10872 KB ok, correct split
38 Correct 14 ms 10864 KB ok, correct split
39 Correct 13 ms 10872 KB ok, correct split
40 Correct 13 ms 10744 KB ok, correct split
41 Correct 12 ms 10716 KB ok, correct split
42 Correct 12 ms 10744 KB ok, correct split
43 Correct 13 ms 10872 KB ok, correct split
44 Correct 13 ms 10872 KB ok, correct split
45 Correct 14 ms 10872 KB ok, correct split
46 Correct 12 ms 10876 KB ok, correct split
47 Incorrect 12 ms 10872 KB answer contains both zero and positive values
48 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 10488 KB ok, correct split
5 Correct 11 ms 10488 KB ok, correct split
6 Correct 14 ms 10488 KB ok, correct split
7 Correct 143 ms 27332 KB ok, correct split
8 Correct 138 ms 25080 KB ok, correct split
9 Correct 135 ms 24568 KB ok, correct split
10 Correct 144 ms 27896 KB ok, correct split
11 Correct 135 ms 27740 KB ok, correct split
12 Correct 11 ms 10488 KB ok, correct split
13 Correct 11 ms 10616 KB ok, correct split
14 Correct 11 ms 10616 KB ok, correct split
15 Correct 152 ms 23644 KB ok, correct split
16 Correct 108 ms 18552 KB ok, correct split
17 Correct 138 ms 27808 KB ok, correct split
18 Correct 134 ms 25008 KB ok, correct split
19 Correct 212 ms 21308 KB ok, correct split
20 Correct 119 ms 20216 KB ok, correct split
21 Correct 74 ms 18068 KB ok, correct split
22 Correct 71 ms 18028 KB ok, correct split
23 Correct 77 ms 18032 KB ok, correct split
24 Correct 11 ms 10616 KB ok, correct split
25 Correct 111 ms 18692 KB ok, correct split
26 Correct 46 ms 13816 KB ok, correct split
27 Correct 11 ms 10616 KB ok, correct split
28 Correct 138 ms 22520 KB ok, correct split
29 Correct 153 ms 22380 KB ok, correct split
30 Correct 125 ms 22136 KB ok, correct split
31 Correct 130 ms 23408 KB ok, correct split
32 Correct 127 ms 21996 KB ok, correct split
33 Correct 38 ms 13176 KB ok, no valid answer
34 Correct 53 ms 14496 KB ok, no valid answer
35 Correct 89 ms 18548 KB ok, no valid answer
36 Incorrect 112 ms 18652 KB answer contains both zero and positive values
37 Halted 0 ms 0 KB -