oj.uz

답안 #828155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828155 2023-08-17T06:06:51 Z jlallas384 낙하산 고리들 (IOI12_rings) C++17
20 / 100
 1664 ms 262144 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 CountCritical(){    
    if(bad) return 0;
    else return ans.size();
}
 
 
 
 
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;
map<int, ufds> mp;

void Link(int a, int b){
    if(bad || ans.size() == 0) return;
    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);
    if(mp.size()){
        set<int> nans;
        for(int x: ans) if(x != a && x != b){
            int bad = 0;
            if(!mp[x].unite(a, b)){
                bad = 1;
            }
            if(!bad) nans.insert(x);
        }
        ans = nans;
    }
    if(!res){
        if(!cyc){
            dfs(a, -1, b);
            ans = {};
            for(int x: path){
                ans.insert(x);
            }
            cyc = 1;
        }else{
            if(mp.size() == 0){
                set<int> nans;
                for(int x: ans){
                    mp[x] = ufds(n);
                    int tbad = 0;
                    for(auto [u, v]: eds){
                        if(u != x && v != x){
                            if(!mp[x].unite(u, v)) tbad = 1;
                        }
                    }
                    if(!tbad) nans.insert(x);
                }
                ans = nans;
            }
        }
    }else{
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 2 ms 964 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 1 ms 824 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 567 ms 92868 KB Output is correct
2 Correct 1083 ms 117752 KB Output is correct
3 Correct 369 ms 108012 KB Output is correct
4 Correct 1384 ms 177272 KB Output is correct
5 Correct 1400 ms 178772 KB Output is correct
6 Correct 1664 ms 208724 KB Output is correct
7 Correct 353 ms 107308 KB Output is correct
8 Correct 1326 ms 159180 KB Output is correct
9 Correct 1494 ms 174612 KB Output is correct
10 Runtime error 1389 ms 262144 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 2 ms 964 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 1 ms 824 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Incorrect 3 ms 1108 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 2 ms 964 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 1 ms 824 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Incorrect 3 ms 1108 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 2 ms 964 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 1 ms 824 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 4 ms 1108 KB Output is correct
11 Correct 567 ms 92868 KB Output is correct
12 Correct 1083 ms 117752 KB Output is correct
13 Correct 369 ms 108012 KB Output is correct
14 Correct 1384 ms 177272 KB Output is correct
15 Correct 1400 ms 178772 KB Output is correct
16 Correct 1664 ms 208724 KB Output is correct
17 Correct 353 ms 107308 KB Output is correct
18 Correct 1326 ms 159180 KB Output is correct
19 Correct 1494 ms 174612 KB Output is correct
20 Runtime error 1389 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -