oj.uz

답안 #828163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828163 2023-08-17T06:10:29 Z jlallas384 낙하산 고리들 (IOI12_rings) C++17
20 / 100
 4000 ms 80176 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;
}

vector<pair<int,int>> eds;


void Link(int a, int b){
    int res = ds.unite(a, b);
    deg[a]++, deg[b]++;
    g[a].push_back(b);
    g[b].push_back(a);
    eds.emplace_back(a, b);
    proc(a), proc(b);
}

int CountCritical(){    
    int fans = 0;
    for(int x: ans){
        ufds f(n);
        int can = 1;
        for(auto [u, v]: eds) if(u != x && v != x){
            if(!f.unite(u, v)) can = 0;
        }
        fans += can;
    }
    return fans;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:85:9: warning: unused variable 'res' [-Wunused-variable]
   85 |     int res = ds.unite(a, b);
      |         ^~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 6 ms 476 KB Output is correct
5 Correct 41 ms 804 KB Output is correct
6 Correct 120 ms 1108 KB Output is correct
7 Correct 1 ms 820 KB Output is correct
8 Correct 102 ms 976 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4045 ms 80176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 6 ms 476 KB Output is correct
5 Correct 41 ms 804 KB Output is correct
6 Correct 120 ms 1108 KB Output is correct
7 Correct 1 ms 820 KB Output is correct
8 Correct 102 ms 976 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 896 ms 1016 KB Output is correct
12 Execution timed out 4067 ms 1828 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 6 ms 476 KB Output is correct
5 Correct 41 ms 804 KB Output is correct
6 Correct 120 ms 1108 KB Output is correct
7 Correct 1 ms 820 KB Output is correct
8 Correct 102 ms 976 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 896 ms 1016 KB Output is correct
12 Execution timed out 4067 ms 1828 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 6 ms 476 KB Output is correct
5 Correct 41 ms 804 KB Output is correct
6 Correct 120 ms 1108 KB Output is correct
7 Correct 1 ms 820 KB Output is correct
8 Correct 102 ms 976 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Execution timed out 4045 ms 80176 KB Time limit exceeded
12 Halted 0 ms 0 KB -