Submission #143452

#	Time	Username	Problem	Language	Result	Execution time	Memory
143452		icypiggy	Split the Attractions (IOI19_split)	C++14	18 / 100	187 ms	27896 KiB

split

#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++;
                        }
                    }
                }
                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 (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36