oj.uz

답안 #143453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143453 2019-08-14T06:25:37 Z icypiggy Split the Attractions (IOI19_split) C++14
18 / 100
 171 ms 37368 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);
                        }
                    }
                }
                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++;
                        }
                    }
                }
                for(int k=0; k<n; k++) {
                    assert(ans[k]!=0);
                }
                return ans;
            }
        }
    }
    assert(false);
    return p;
}
// note parent here means a different thing oops
int findset(int x) {
    return parent[x]==x ? x : parent[x] = findset(parent[x]);
}
void onion(int x, int y) {
    parent[findset(x)] = parent[findset(y)];
}

void verify_ans(int n, int a, int b, int c, vector<int> p, vector<int> q, vector<int> ans) {
    if(ans[0]!=0) {
        int good = 0;
        for(int i=0; i<n; i++) parent[i] = i;
        int onion_count[4] = {0,a-1,b-1,c-1};
        for(int i=0; i<(int) p.size(); i++) {
            if(ans[p[i]]==ans[q[i]] && findset(p[i])!=findset(q[i])) {
                onion(p[i], q[i]);
                onion_count[ans[p[i]]]--;
                if(onion_count[ans[p[i]]]==0) good++;
            }
        }
        int counter[4] = {0,a,b,c};
        for(int i:ans) {
            counter[i]--;
        }
        assert(counter[1]==0);
        assert(counter[2]==0);
        assert(counter[3]==0);
        assert(good>=2);
    } else {
        //assert(false);
    }
}
pair<vector<int>, vector<int>> gen_graph(int n) {
    bool adj[n][n];
    int components = n;
    vector<int> p;
    vector<int> q;
    for(int i=0; i<n; i++) parent[i] = i;
    while(true) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<i; j++) {
                if((rand()%100==0) && adj[i][j]==false) {
                    if(findset(i)!=findset(j)) {
                        adj[i][j] = true;
                        onion(i,j);
                        p.push_back(i);
                        q.push_back(j);
                        components--;
                        if(components==1) {
                            for(int i=0; i<p.size(); i++) {
                                //cout << p[i] << " " << q[i] << "\n";
                            }
                            return make_pair(p,q);
                        }
                        // this generates random trees
                    }
                }
            }
        }
    }
}

Compilation message

split.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > gen_graph(int)':
split.cpp:208:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             for(int i=0; i<p.size(); i++) {
                                          ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10616 KB ok, correct split
2 Correct 11 ms 10488 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 10492 KB ok, correct split
7 Correct 134 ms 27388 KB ok, correct split
8 Correct 137 ms 25080 KB ok, correct split
9 Correct 133 ms 24428 KB ok, correct split
10 Correct 137 ms 27768 KB ok, correct split
11 Correct 134 ms 27800 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 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 23672 KB ok, correct split
5 Correct 109 ms 18556 KB ok, correct split
6 Correct 134 ms 27768 KB ok, correct split
7 Correct 129 ms 24996 KB ok, correct split
8 Correct 171 ms 21212 KB ok, correct split
9 Correct 121 ms 19960 KB ok, correct split
10 Correct 75 ms 18024 KB ok, correct split
11 Correct 72 ms 18032 KB ok, correct split
12 Correct 83 ms 18020 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 10488 KB ok, correct split
2 Correct 113 ms 18672 KB ok, correct split
3 Correct 46 ms 13816 KB ok, correct split
4 Correct 11 ms 10616 KB ok, correct split
5 Correct 120 ms 22520 KB ok, correct split
6 Correct 123 ms 22236 KB ok, correct split
7 Correct 124 ms 22136 KB ok, correct split
8 Correct 134 ms 23568 KB ok, correct split
9 Correct 125 ms 21944 KB ok, correct split
10 Correct 37 ms 13176 KB ok, no valid answer
11 Correct 52 ms 14552 KB ok, no valid answer
12 Correct 86 ms 18408 KB ok, no valid answer
13 Runtime error 137 ms 37368 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 13 ms 10488 KB ok, no valid answer
3 Correct 11 ms 10488 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 10580 KB ok, correct split
7 Correct 11 ms 10616 KB ok, correct split
8 Correct 11 ms 10616 KB ok, correct split
9 Correct 14 ms 10872 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 10616 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 10616 KB ok, correct split
17 Correct 13 ms 10616 KB ok, correct split
18 Correct 13 ms 10616 KB ok, correct split
19 Correct 11 ms 10616 KB ok, correct split
20 Correct 14 ms 10744 KB ok, correct split
21 Correct 15 ms 10872 KB ok, correct split
22 Correct 13 ms 10872 KB ok, correct split
23 Correct 16 ms 10872 KB ok, correct split
24 Correct 12 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 11 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 14 ms 10588 KB ok, correct split
34 Correct 13 ms 10744 KB ok, correct split
35 Correct 13 ms 10744 KB ok, correct split
36 Correct 13 ms 10708 KB ok, correct split
37 Correct 14 ms 10872 KB ok, correct split
38 Correct 14 ms 10872 KB ok, correct split
39 Correct 14 ms 10760 KB ok, correct split
40 Correct 13 ms 10872 KB ok, correct split
41 Correct 12 ms 10744 KB ok, correct split
42 Correct 12 ms 10744 KB ok, correct split
43 Correct 13 ms 10872 KB ok, correct split
44 Correct 14 ms 10872 KB ok, correct split
45 Correct 13 ms 10872 KB ok, correct split
46 Correct 12 ms 10872 KB ok, correct split
47 Runtime error 25 ms 21752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 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 10488 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 10492 KB ok, correct split
7 Correct 134 ms 27388 KB ok, correct split
8 Correct 137 ms 25080 KB ok, correct split
9 Correct 133 ms 24428 KB ok, correct split
10 Correct 137 ms 27768 KB ok, correct split
11 Correct 134 ms 27800 KB ok, correct split
12 Correct 12 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 23672 KB ok, correct split
16 Correct 109 ms 18556 KB ok, correct split
17 Correct 134 ms 27768 KB ok, correct split
18 Correct 129 ms 24996 KB ok, correct split
19 Correct 171 ms 21212 KB ok, correct split
20 Correct 121 ms 19960 KB ok, correct split
21 Correct 75 ms 18024 KB ok, correct split
22 Correct 72 ms 18032 KB ok, correct split
23 Correct 83 ms 18020 KB ok, correct split
24 Correct 13 ms 10488 KB ok, correct split
25 Correct 113 ms 18672 KB ok, correct split
26 Correct 46 ms 13816 KB ok, correct split
27 Correct 11 ms 10616 KB ok, correct split
28 Correct 120 ms 22520 KB ok, correct split
29 Correct 123 ms 22236 KB ok, correct split
30 Correct 124 ms 22136 KB ok, correct split
31 Correct 134 ms 23568 KB ok, correct split
32 Correct 125 ms 21944 KB ok, correct split
33 Correct 37 ms 13176 KB ok, no valid answer
34 Correct 52 ms 14552 KB ok, no valid answer
35 Correct 86 ms 18408 KB ok, no valid answer
36 Runtime error 137 ms 37368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Halted 0 ms 0 KB -