oj.uz

Submission #1013356

# Submission time Handle Problem Language Result Execution time Memory
1013356 2024-07-03T12:50:43 Z Ludissey Parachute rings (IOI12_rings) C++14
0 / 100
 729 ms 141588 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)
    if(sz(neigh[A])==3||sz(neigh[B])==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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 0 ms 780 KB Output is correct
8 Incorrect 2 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 49232 KB Output is correct
2 Correct 457 ms 75344 KB Output is correct
3 Correct 629 ms 96784 KB Output is correct
4 Correct 600 ms 107600 KB Output is correct
5 Correct 657 ms 109204 KB Output is correct
6 Correct 729 ms 141588 KB Output is correct
7 Correct 596 ms 107228 KB Output is correct
8 Correct 588 ms 100820 KB Output is correct
9 Correct 631 ms 107496 KB Output is correct
10 Incorrect 463 ms 105552 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 0 ms 780 KB Output is correct
8 Incorrect 2 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 0 ms 780 KB Output is correct
8 Incorrect 2 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 0 ms 780 KB Output is correct
8 Incorrect 2 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -