Submission #874938

#	Time	Username	Problem	Language	Result	Execution time	Memory
874938		tuannm	Split the Attractions (IOI19_split)	C++17	40 / 100	82 ms	24572 KiB

split

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const string NAME = "";
const int lim = 2147483647;
//const unsigned int lim = 4294967295;
//const long long lim = 9223372036854775807;
//const unsigned long long lim = 18446744073709551615;
const int mset = 0x3f;
const double pi = acos(-1);
int n, m;
ii ar[4];
vector<int> adj[N], g[N];
int pa[N], sz[N], spec = -1, spec2, accu;
int ans[N];
bool visited[N], marked[N], used_so_far[N], have_rev[N];
queue<int> q1, q2;

void build(int u){
    sz[u] = 1;
    visited[u] = true;
    for(auto v : g[u]){
        if(visited[v]){
            have_rev[u] = true;
            continue;
        }
        pa[v] = u;
        adj[u].pb(v);
        adj[v].pb(u);
        build(v);
        sz[u] += sz[v];
    }
}

void find_node_DFS(int u){
    bool haha = true;
    if(sz[u] < ar[1].fi)
        haha = false;
    for(auto v : adj[u]){
        if(v == pa[u] || marked[v])
            continue;
        if(sz[v] >= ar[1].fi)
            haha = false;
        find_node_DFS(v);

    }
    if(haha){
        if(spec == -1 || sz[spec] > sz[u])
            spec = u;
    }
}

void subtree_find_DFS(int u){
    bool haha = true;
    if(sz[spec] - sz[u] < ar[1].fi || !have_rev[u])
        haha = false;
    for(auto v : adj[u]){
        if(v == pa[u])
            continue;
        subtree_find_DFS(v);
    }
    if(haha){
        if(spec2 == -1 || sz[spec2] < sz[u])
            spec2 = u;
    }
}

void get_node_DFS(int u){
    for(auto v : adj[u]){
        if(v == pa[u] || marked[v])
            continue;
        get_node_DFS(v);
    }
    q1.push(u);
}

void second_type_DFS(int u){
    visited[u] = true;
    for(auto v : g[u]){
        if(used_so_far[v] || visited[v])
            continue;
        second_type_DFS(v);
    }
    q2.push(u);
}

/*
void inp(){
    cin >> n >> m;
    for(int i = 1; i < 4; ++i){
        cin >> ar[i].fi;
        ar[i].se = i;
    }
    for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
}

void solve(){
    build(0);
    sort(ar + 1, ar + 4);
    find_node_DFS(0);
    memset(visited, false, sizeof(visited));
    if(n - sz[spec] >= ar[1].fi){
        if(m > n - 1){
            while(spec2 != -1){
                spec2 = -1;
                subtree_find_DFS(spec);
                if(spec2 != -1){
                    marked[spec2] = true;
                    int tmp = spec2;
                    while(tmp != spec){
                        sz[pa[tmp]] -= sz[spec2];
                        tmp = pa[tmp];
                    }
                }
            }
        }
        get_node_DFS(spec);
        if(sz[spec] > n - sz[spec])
            swap(ar[1], ar[2]);
        while(q1.size() > ar[1].fi)
            q1.pop();
        while(!q1.empty()){
            int u = q1.front();
            q1.pop();
            ans[u] = ar[1].se;
            used_so_far[u] = true;
        }
        second_type_DFS(0);
        if(q2.size() < ar[2].fi){
            for(int i = 0; i < n; ++i)
                ans[i] = 0;
        }
        else{
            while(q2.size() > ar[2].fi)
                q2.pop();
            while(!q2.empty()){
                int u = q2.front();
                q2.pop();
                ans[u] = ar[2].se;
                used_so_far[u] = true;
            }
            for(int i = 0; i < n; ++i){
                if(used_so_far[i])
                    continue;
                ans[i] = ar[3].se;
            }
        }
    }
    for(int i = 0; i < n; ++i)
        cout << ans[i] << " ";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}
*/

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
    m = p.size();
    ar[1] = {a, 1};
    ar[2] = {b, 2};
    ar[3] = {c, 3};
    for(int i = 1; i <= m; ++i){
        int u = p[i - 1], v = q[i - 1];
        g[u].pb(v);
        g[v].pb(u);
    }
    build(0);
    sort(ar + 1, ar + 4);
    vector<int> ans(n, 0);
    find_node_DFS(0);
    memset(visited, false, sizeof(visited));
    if(n - sz[spec] >= ar[1].fi){
        if(m > n - 1){
            while(spec2 != -1){
                spec2 = -1;
                subtree_find_DFS(spec);
                if(spec2 != -1){
                    marked[spec2] = true;
                    int tmp = spec2;
                    while(tmp != spec){
                        sz[pa[tmp]] -= sz[spec2];
                        tmp = pa[tmp];
                    }
                }
            }
        }
        get_node_DFS(spec);
        if(sz[spec] > n - sz[spec])
            swap(ar[1], ar[2]);
        while(q1.size() > ar[1].fi)
            q1.pop();
        while(!q1.empty()){
            int u = q1.front();
            q1.pop();
            ans[u] = ar[1].se;
            used_so_far[u] = true;
        }
        second_type_DFS(0);
        if(q2.size() < ar[2].fi){
            for(int i = 0; i < n; ++i)
                ans[i] = 0;
        }
        else{
            while(q2.size() > ar[2].fi)
                q2.pop();
            while(!q2.empty()){
                int u = q2.front();
                q2.pop();
                ans[u] = ar[2].se;
                used_so_far[u] = true;
            }
            for(int i = 0; i < n; ++i){
                if(used_so_far[i])
                    continue;
                ans[i] = ar[3].se;
            }
        }
    }
    return ans;
}

/*
10 9
2 4 4
0 4
4 7
8 6
4 1
2 7
0 3
8 9
8 4
9 5
*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:212:25: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  212 |         while(q1.size() > ar[1].fi)
      |                         ^
split.cpp:221:22: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  221 |         if(q2.size() < ar[2].fi){
      |                      ^
split.cpp:226:29: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  226 |             while(q2.size() > ar[2].fi)
      |                             ^

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