oj.uz

Submission #1013354

# Submission time Handle Problem Language Result Execution time Memory
1013354 2024-07-03T12:49:24 Z Ludissey Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 118956 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) {
    cerr << A << " " << B << "\n";
    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 1 ms 604 KB Output is correct
2 Correct 18 ms 940 KB Output is correct
3 Correct 32 ms 992 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 12 ms 860 KB Output is correct
6 Correct 21 ms 1220 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Incorrect 16 ms 856 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2285 ms 63200 KB Output is correct
2 Correct 3554 ms 97144 KB Output is correct
3 Execution timed out 4067 ms 118956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 18 ms 940 KB Output is correct
3 Correct 32 ms 992 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 12 ms 860 KB Output is correct
6 Correct 21 ms 1220 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Incorrect 16 ms 856 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 18 ms 940 KB Output is correct
3 Correct 32 ms 992 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 12 ms 860 KB Output is correct
6 Correct 21 ms 1220 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Incorrect 16 ms 856 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 18 ms 940 KB Output is correct
3 Correct 32 ms 992 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 12 ms 860 KB Output is correct
6 Correct 21 ms 1220 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Incorrect 16 ms 856 KB Output isn't correct
9 Halted 0 ms 0 KB -