oj.uz

답안 #1013369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013369 2024-07-03T12:59:54 Z Ludissey 낙하산 고리들 (IOI12_rings) C++14
37 / 100
 794 ms 139136 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
int n;
bool hasloop=false;
vector<vector<int>> neigh;
vector<int> visited;
vector<int> parent;
vector<int> pr;
vector<int> sz;
vector<int> crit;
vector<int> incycle;
int timer=0;
int exceptation=-1;
bool cycl=0;
int cc=0;
int c=0;
int upds=0;

int getParent(int a) { return parent[a]==a ? a : parent[a]=getParent(parent[a]); }

void unite(int a, int b){
    a=getParent(a); b=getParent(b);
    if(a==b) return;
    if(sz[b]>sz[a]) swap(a,b);
    sz[a]+=sz[b];
    parent[a]=b;
}

void detect_cycle(int x, int p) {
    if(visited[x]==2) return;
    if (visited[x] == 1) {
        vector<int> v;
        incycle.push_back(x);
        int cr=pr[x];
        while (cr!=x) {
            incycle.push_back(cr);
            cr=pr[cr];
        } 
        return;
    }
    pr[x]=p;
    visited[x]=1;
    for (int to : neigh[x]) {
        if (to==p) continue;
        detect_cycle(to,x);
    }
    visited[x]=2;
}

void Init(signed N_) {
    n = N_;
    parent.resize(n);
    visited.resize(n,0);
    neigh.resize(n);
    cc=0;
    sz.resize(n,1);
    pr.resize(n,-1);
    crit.resize(n,0);
    upds=0;
    for (int i = 0; i < n; i++) parent[i]=i;
}


void case1(int A, int B){ //two vertex of different sets O(1);
    unite(A,B);
    if(sz(neigh[A])==3){
        crit[neigh[A][0]]++;
        crit[neigh[A][1]]++;
        crit[neigh[A][2]]++;
        crit[A]++;
        upds++;
    }else if(sz(neigh[A])>3){
        crit[A]++;
        upds++;
    }
    if(sz(neigh[B])==3){
        crit[neigh[B][0]]++;
        crit[neigh[B][1]]++;
        crit[neigh[B][2]]++;
        crit[B]++;
        upds++;
    }else if(sz(neigh[B])>3){
        crit[B]++;
        upds++;
    }
}
void case2(int A, int B){ //two vertex of same sets !! NO CYCLE !! O(N+M)
    detect_cycle(A,B);
    cycl=1;
    for (int i = 0; i < sz(incycle); i++) crit[incycle[i]]++;
    upds++;
    case1(A,B);
}
void case3(int A, int B){ //two vertex of same sets !! CYCLE !! O(1)
    //cerr << "case 3";
    crit[A]++;
    crit[B]++;
    upds++;
    if(sz(neigh[A])>3){
        crit[A]++;
        upds++;
    }
    if(sz(neigh[B])>3){
        crit[B]++;
        upds++;
    }
}
void Link(signed A, signed B) {
    neigh[A].push_back(B);
    neigh[B].push_back(A);
    if(getParent(A)==getParent(B)){
        if(cycl) case3(A,B);
        else case2(A,B);
    }else{
        case1(A,B);
    }
}

signed CountCritical() {
    c=0;
    for (int i = 0; i < n; i++) if(crit[i]==upds) c++;
    return c;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 55636 KB Output is correct
2 Correct 459 ms 85268 KB Output is correct
3 Correct 629 ms 107580 KB Output is correct
4 Correct 616 ms 106724 KB Output is correct
5 Correct 633 ms 108240 KB Output is correct
6 Correct 794 ms 139136 KB Output is correct
7 Correct 615 ms 106116 KB Output is correct
8 Correct 612 ms 99676 KB Output is correct
9 Correct 659 ms 106428 KB Output is correct
10 Correct 418 ms 104408 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 3 ms 1464 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Incorrect 5 ms 1368 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 3 ms 1464 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Incorrect 5 ms 1368 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 209 ms 55636 KB Output is correct
12 Correct 459 ms 85268 KB Output is correct
13 Correct 629 ms 107580 KB Output is correct
14 Correct 616 ms 106724 KB Output is correct
15 Correct 633 ms 108240 KB Output is correct
16 Correct 794 ms 139136 KB Output is correct
17 Correct 615 ms 106116 KB Output is correct
18 Correct 612 ms 99676 KB Output is correct
19 Correct 659 ms 106428 KB Output is correct
20 Correct 418 ms 104408 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 3 ms 1464 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Incorrect 5 ms 1368 KB Output isn't correct
25 Halted 0 ms 0 KB -