oj.uz

답안 #799291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799291 2023-07-31T12:00:03 Z jlallas384 낙하산 고리들 (IOI12_rings) C++17
20 / 100
 4000 ms 177232 KB 
#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;
    if(cyc){
        set<int> gds;
        int cnts = 0;
        for(int i = 0; i < n; i++){
            cnts += deg[i] >= 3;
        }
        for(int v: ans){
            vector<int> vis(n);
            vis[v] = 1;
            int ok = 1;
            int t = cnts - (deg[v] >= 3);
            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);
            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{
            if(ans.size() > 2) bad = 1;
            return;
        }
    }else{
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
}

Compilation message

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:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         assert(tot == ans.size());
      |                ~~~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 74 ms 944 KB Output is correct
6 Correct 389 ms 1540 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 544 ms 93292 KB Output is correct
2 Correct 1076 ms 121392 KB Output is correct
3 Correct 393 ms 115132 KB Output is correct
4 Execution timed out 4098 ms 177232 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 74 ms 944 KB Output is correct
6 Correct 389 ms 1540 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Incorrect 5 ms 1108 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 74 ms 944 KB Output is correct
6 Correct 389 ms 1540 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Incorrect 5 ms 1108 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 74 ms 944 KB Output is correct
6 Correct 389 ms 1540 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 544 ms 93292 KB Output is correct
12 Correct 1076 ms 121392 KB Output is correct
13 Correct 393 ms 115132 KB Output is correct
14 Execution timed out 4098 ms 177232 KB Time limit exceeded
15 Halted 0 ms 0 KB -