Submission #799295

#	Time	Username	Problem	Language	Result	Execution time	Memory
799295		jlallas384	Parachute rings (IOI12_rings)	C++17	0 / 100	4083 ms	90024 KiB

rings

#include <bits/stdc++.h>
using namespace std;



struct ufds{
    vector<int> sz, par;
    ufds(){}
    ufds(int n): sz(n, 1), par(n){
        iota(par.begin(), par.end(), 0);
    }
    int find(int a){
        return par[a] == a ? a : par[a] = find(par[a]);
    }
    int unite(int a, int b){
        a = find(a), b = find(b);
        if(a == b) return 0;
        if(sz[a] < sz[b]) swap(a, b);
        par[b] = a;
        sz[a] += sz[b];
        return 1;
    }
};

set<int> ans;
vector<vector<int>> g, tree;
vector<int> deg;
int n;
ufds ds;

int bad = 0;
int d4 = 0;

void Init(int N){
    n = N;
    g.resize(n);
    tree.resize(n);
    deg.resize(n);
    for(int i = 0; i < n; i++){
        ans.insert(i);
    }
    ds = ufds(n);
}

void proc(int a, int add = 1){
    if(deg[a] == 4){
        if(add){
            d4++;
            if(d4 == 2) bad = 1;
        }
        if(!ans.count(a)) ans = {};
        else ans = {a};
    }else if(deg[a] == 3){
        set<int> nans;
        if(ans.count(a)) nans.insert(a);
        for(int u: g[a]){
            if(ans.count(u)) nans.insert(u);
        }
        ans = nans;
    }
}
int cyc = 0;

vector<int> path;
int dfs(int v, int p, int x){
    path.push_back(v);
    if(v == x) return 1;
    for(int u: tree[v]) if(u != p){
        if(dfs(u, v, x)) return 1;
    }
    path.pop_back();
    return 0;
}

int dfs2(int v, vector<int> &vis, int p){
    vis[v] = 2;
    for(int u: g[v]){
        if(!vis[u]){
            if(dfs2(u, vis, v)) return 1;
        }
        else if(vis[u] == 2 && u != p){
            return 1;
        }
    }
    return 0;
}
int cancer = -1;
int CountCritical(){    
    if(bad) return 0;
    if(ans.size() == 0) return 0;
    int tot = 0;
    set<int> gds;
    int cnts = 0;
    for(int i = 0; i < n; i++){
        cnts += deg[i] >= 3;
    }
    for(int v: ans){
        int ok = 1;
        int t = cnts - (deg[v] >= 3);
        if(deg[v] != 2){
            vector<int> vis(n);
            vis[v] = 1;
            for(int u: g[v]){
                t -= (deg[u] == 3);
            }
            for(int i = 0; i < n; i++){
                if(!vis[i] && dfs2(i, vis, -1)){
                    ok = 0;
                }
            }
        }
        ok &= (t == 0 || deg[v] == 2);
        tot += ok;
        if(ok) gds.insert(v);
    }
    if(tot == 0) bad = 1;
    cancer = tot;
    assert(gds == ans);
    assert(tot == ans.size());
    if(bad) return 0;
    else if(!cyc) return ans.size();
    return tot;
}






void Link(int a, int b){
    if(bad) return;
    int res = ds.unite(a, b);
    deg[a]++, deg[b]++;
    g[a].push_back(b);
    g[b].push_back(a);
    proc(a), proc(b);
    if(!res){
        if(!cyc){
            dfs(a, -1, b);
            ans = {};
            for(int x: path){
                ans.insert(x);
            }
            for(int i = 0; i < n; i++){
                proc(i);
            }
            cyc = 1;
        }else{

        }
    }else{
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from rings.cpp:1:
rings.cpp: In function 'int CountCritical()':
rings.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     assert(tot == ans.size());
      |            ~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31