oj.uz

답안 #143457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143457 2019-08-14T06:37:13 Z icypiggy Split the Attractions (IOI19_split) C++14
18 / 100
 224 ms 37428 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

# 결과 실행 시간 메모리 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 11 ms 10488 KB ok, correct split
7 Correct 128 ms 27384 KB ok, correct split
8 Correct 134 ms 25132 KB ok, correct split
9 Correct 135 ms 24540 KB ok, correct split
10 Correct 138 ms 27788 KB ok, correct split
11 Correct 137 ms 27768 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10488 KB ok, correct split
2 Correct 11 ms 10616 KB ok, correct split
3 Correct 13 ms 10616 KB ok, correct split
4 Correct 149 ms 23572 KB ok, correct split
5 Correct 116 ms 18524 KB ok, correct split
6 Correct 136 ms 27744 KB ok, correct split
7 Correct 126 ms 25080 KB ok, correct split
8 Correct 224 ms 21240 KB ok, correct split
9 Correct 124 ms 20164 KB ok, correct split
10 Correct 76 ms 18032 KB ok, correct split
11 Correct 71 ms 18032 KB ok, correct split
12 Correct 76 ms 18060 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10616 KB ok, correct split
2 Correct 105 ms 18552 KB ok, correct split
3 Correct 44 ms 13816 KB ok, correct split
4 Correct 12 ms 10616 KB ok, correct split
5 Correct 135 ms 22556 KB ok, correct split
6 Correct 130 ms 22264 KB ok, correct split
7 Correct 132 ms 22136 KB ok, correct split
8 Correct 133 ms 23544 KB ok, correct split
9 Correct 129 ms 22008 KB ok, correct split
10 Correct 39 ms 13304 KB ok, no valid answer
11 Correct 53 ms 14584 KB ok, no valid answer
12 Correct 91 ms 18532 KB ok, no valid answer
13 Runtime error 109 ms 37428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10488 KB ok, correct split
2 Correct 11 ms 10488 KB ok, no valid answer
3 Correct 11 ms 10488 KB ok, correct split
4 Correct 12 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 11 ms 10616 KB ok, correct split
8 Correct 11 ms 10516 KB ok, correct split
9 Correct 16 ms 10872 KB ok, correct split
10 Correct 14 ms 10872 KB ok, correct split
11 Correct 12 ms 10616 KB ok, correct split
12 Correct 14 ms 10772 KB ok, correct split
13 Correct 11 ms 10536 KB ok, correct split
14 Correct 11 ms 10488 KB ok, correct split
15 Correct 11 ms 10616 KB ok, correct split
16 Correct 11 ms 10488 KB ok, correct split
17 Correct 11 ms 10616 KB ok, correct split
18 Correct 11 ms 10616 KB ok, correct split
19 Correct 18 ms 10744 KB ok, correct split
20 Correct 10 ms 10616 KB ok, correct split
21 Correct 13 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 10744 KB ok, correct split
27 Correct 13 ms 10744 KB ok, correct split
28 Correct 13 ms 10744 KB ok, correct split
29 Correct 13 ms 10616 KB ok, correct split
30 Correct 13 ms 10744 KB ok, correct split
31 Correct 11 ms 10616 KB ok, correct split
32 Correct 11 ms 10616 KB ok, correct split
33 Correct 11 ms 10616 KB ok, correct split
34 Runtime error 26 ms 21596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 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 11 ms 10488 KB ok, correct split
7 Correct 128 ms 27384 KB ok, correct split
8 Correct 134 ms 25132 KB ok, correct split
9 Correct 135 ms 24540 KB ok, correct split
10 Correct 138 ms 27788 KB ok, correct split
11 Correct 137 ms 27768 KB ok, correct split
12 Correct 10 ms 10488 KB ok, correct split
13 Correct 11 ms 10616 KB ok, correct split
14 Correct 13 ms 10616 KB ok, correct split
15 Correct 149 ms 23572 KB ok, correct split
16 Correct 116 ms 18524 KB ok, correct split
17 Correct 136 ms 27744 KB ok, correct split
18 Correct 126 ms 25080 KB ok, correct split
19 Correct 224 ms 21240 KB ok, correct split
20 Correct 124 ms 20164 KB ok, correct split
21 Correct 76 ms 18032 KB ok, correct split
22 Correct 71 ms 18032 KB ok, correct split
23 Correct 76 ms 18060 KB ok, correct split
24 Correct 11 ms 10616 KB ok, correct split
25 Correct 105 ms 18552 KB ok, correct split
26 Correct 44 ms 13816 KB ok, correct split
27 Correct 12 ms 10616 KB ok, correct split
28 Correct 135 ms 22556 KB ok, correct split
29 Correct 130 ms 22264 KB ok, correct split
30 Correct 132 ms 22136 KB ok, correct split
31 Correct 133 ms 23544 KB ok, correct split
32 Correct 129 ms 22008 KB ok, correct split
33 Correct 39 ms 13304 KB ok, no valid answer
34 Correct 53 ms 14584 KB ok, no valid answer
35 Correct 91 ms 18532 KB ok, no valid answer
36 Runtime error 109 ms 37428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Halted 0 ms 0 KB -