Submission #152398

#	Time	Username	Problem	Language	Result	Execution time	Memory
152398		crackersamdjam	Split the Attractions (IOI19_split)	C++14	0 / 100	5 ms	2808 KiB

split

#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
const int MM = 1e5+2;

vector<int> adj[MM];
vector<int> ans;
int sz[MM], dfn[MM], low[MM], t, par[MM];
int a, b, c, first = -1, purple;
int aa = 1, ab = 2, ac = 3;

void fill(int cur, int &rem, int v){
    //printf("f "); print(cur, rem, v);
    if(!rem || ans[cur])
        return;
    ans[cur] = v;
    rem--;
    for(int u: adj[cur]){
        if(dfn[u] > dfn[cur] && low[u] >= dfn[cur])
            fill(u, rem, v);
    }
}

void free_fill(int cur, int &rem, int v){
    //printf("ff "); print(cur, rem, v);
    if(!rem || ans[cur])
        return;
    ans[cur] = v;
    rem--;
    for(int u: adj[cur]){
        free_fill(u, rem, v);
    }
}

void fill_down(int cur, int &rem, int v){
    //printf("fd "); print(cur, rem, v);
    if(!rem || ans[cur])
        return;
    ans[cur] = v;
    rem--;
    for(int u: adj[cur]){
        if(dfn[u] > dfn[cur])
            fill_down(u, rem, v);
    }
}

int dfs(int cur, int pre){
    print(cur, pre);
    
    if(cur)
        par[cur] = pre;
    sz[cur] = 1;
    dfn[cur] = low[cur] = ++t;
    
    for(int u: adj[cur]){
        if(u == pre)
            continue;
        
        if(!dfn[u]){
            sz[cur] += dfs(u, cur);
            low[cur] = min(low[cur], low[u]);
        }
        else
            low[cur] = min(low[cur], dfn[u]);
    }
    
    if(first == -1 && sz[cur] >= a){
        //printf("do %d\n", cur);
        for(int u: adj[cur]){
            if(dfn[u] > dfn[cur] && low[u] >= dfn[cur]){
                purple += sz[u];
            }
        }
        if(purple > b+c)
            return first = -2;
        
        first = cur;
    }
    
    return sz[cur];
}

vector<int> find_split(int n, int ia, int ib, int ic, vector<int> p, vector<int> q){
    a = ia, b = ib, c = ic;
    ans.resize(n);
    
    for(int i = 0; i < p.size(); i++){
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    
    if(a > b)
        swap(a, b), swap(aa, ab);
    if(b > c)
        swap(b, c), swap(ab, ac);
    if(a > b)
        swap(a, b), swap(aa, ab);
    
    assert(a <= b && b <= c);
    //print(a, b, c, aa, ab, ac);
    
    dfs(0, -1);
    
    fflush(stdout);
    assert(first != -1);
    if(first == -2)
        return ans;
    
    if(purple >= b){
        fill(first, b, ab);
        free_fill(par[first], a, aa);
    }
    else{
        fill(first, a, aa);
        for(int u: adj[first]){
            if(u != par[first])
                fill_down(u, a, aa);
        }
        //printf("a %d\n", a);
        assert(a == 0);
        free_fill(par[first], b, ab);
    }
    
    assert(a == 0);
    assert(b == 0);
    
    for(int &i: ans){
        if(!i)
            i = ac;
    }
    
    return ans;
}



/*
 * tree
 * make sure that a subtree is larger than smallest [a, b, c]
 * the second smallest can go through centroid
 * and remaining nodes go to largeststd::vector<int> find_split(int n, int a, int b, int c, std::vector<int>p, std::vector<int>q)
 *
 * policija tarjan dfs tree to get dfn and low
 * if(size[u] >= a)
 *      if dfn[v] > dfn[u] && low[v] >= dfn[u]
 *
 * if purple > b+c
 *      impossible
 * if purple >= b
 *      make it b
 * else make it a
 *      borrow red while needed
 *      take children of u
 */

Compilation message (stderr)

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

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