oj.uz

Submission #760697

# Submission time Handle Problem Language Result Execution time Memory
760697 2023-06-18T07:32:38 Z fatemetmhr Parachute rings (IOI12_rings) C++17
37 / 100
 1109 ms 87392 KB 
//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e6   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n;
bool found = false;
bool cy = false, morecy = false, mark[maxn5];
int cynum = 0, cnt[maxn5], q[maxn5];
vector <int> adj[maxn5];


inline void calc(){
    int l = 0, r = 0;
    memset(mark, false, sizeof mark);
    for(int i = 0; i < n; i++){
        cnt[i] = adj[i].size();
        if(cnt[i] < 2){
            mark[i] = true;
            q[r++] = i;
        }
    }
    while(l < r){
        int v = q[l++];
        for(auto u : adj[v]) if(!mark[u]){
            cnt[u]--;
            if(cnt[u] < 2){
                mark[u] = true;
                q[r++] = u;
            }
        }
    }
    cynum = 0;
    for(int i = 0; i < n; i++)
        cynum += (!mark[i]);
    memset(mark, false, sizeof mark);
}

struct _dsu{

    int remver, par[maxn5];
    bool noans;

    _dsu(){
        remver = -1;
        noans = false;
        memset(par, -1, sizeof par);
    }

    int get_par(int a){return par[a] < 0 ? a : par[a] = get_par(par[a]);}

    inline void add(int a, int b){
        if(a == remver || b == remver || a == b)
            return;
        a = get_par(a);
        b = get_par(b);
        if(a == b){
            noans = true;
            if(cy)
                morecy = true;
            else{
                cy = true;
                if(remver == -1)
                    calc();
            }
            return;
        }
        if(-par[a] < -par[b])
            swap(a, b);
        par[a] += par[b];
        par[b] = a;
    }

} dsu[6];


void Init(int N_) {
    n = N_;
}

void Link(int a, int b){
    adj[a].pb(b);
    adj[b].pb(a);
    dsu[0].add(a, b);
    if(found) for(int i = 1; i < 5; i++)
        dsu[i].add(a, b);
    if(!found && adj[a].size() == 3){
        found = true;
        dsu[1].remver = a;
        for(int i = 0; i < 3; i++){
            dsu[i + 2].remver = adj[a][i];
            for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
                dsu[i + 2].add(v, u);
        }
    }
    else if(adj[a].size() == 3){
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
        for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
            dsu[i].noans = true;
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
    }
    else if(adj[a].size() == 4){
        for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
            dsu[i].noans = true;
    }
    swap(a, b);
    if(!found && adj[a].size() == 3){
        found = true;
        dsu[1].remver = a;
        for(int i = 0; i < 3; i++){
            dsu[i + 2].remver = adj[a][i];
            for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
                dsu[i + 2].add(v, u);
        }
    }
    else if(adj[a].size() == 3){
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
        for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
            dsu[i].noans = true;
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
    }
    else if(adj[a].size() == 4){
        for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
            dsu[i].noans = true;
    }
}

int CountCritical() {

    if(found){
        int num = 0;
        for(int i = 1; i < 5; i++) 
            num += (!dsu[i].noans);
        return num;
    }
    if(!cy)
        return n;
    if(morecy)
        return 0;
    return cynum;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 23 ms 47424 KB Output is correct
3 Correct 23 ms 47444 KB Output is correct
4 Correct 21 ms 48212 KB Output is correct
5 Correct 23 ms 48272 KB Output is correct
6 Correct 24 ms 48468 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 24 ms 48444 KB Output is correct
9 Correct 23 ms 47372 KB Output is correct
10 Correct 22 ms 47412 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 63724 KB Output is correct
2 Correct 768 ms 72296 KB Output is correct
3 Correct 1109 ms 83260 KB Output is correct
4 Correct 773 ms 87300 KB Output is correct
5 Correct 751 ms 87392 KB Output is correct
6 Correct 689 ms 84432 KB Output is correct
7 Correct 966 ms 82716 KB Output is correct
8 Correct 916 ms 76676 KB Output is correct
9 Correct 964 ms 78516 KB Output is correct
10 Correct 472 ms 85572 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 23 ms 47424 KB Output is correct
3 Correct 23 ms 47444 KB Output is correct
4 Correct 21 ms 48212 KB Output is correct
5 Correct 23 ms 48272 KB Output is correct
6 Correct 24 ms 48468 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 24 ms 48444 KB Output is correct
9 Correct 23 ms 47372 KB Output is correct
10 Correct 22 ms 47412 KB Output is correct
11 Incorrect 26 ms 48488 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 23 ms 47424 KB Output is correct
3 Correct 23 ms 47444 KB Output is correct
4 Correct 21 ms 48212 KB Output is correct
5 Correct 23 ms 48272 KB Output is correct
6 Correct 24 ms 48468 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 24 ms 48444 KB Output is correct
9 Correct 23 ms 47372 KB Output is correct
10 Correct 22 ms 47412 KB Output is correct
11 Incorrect 26 ms 48488 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 23 ms 47424 KB Output is correct
3 Correct 23 ms 47444 KB Output is correct
4 Correct 21 ms 48212 KB Output is correct
5 Correct 23 ms 48272 KB Output is correct
6 Correct 24 ms 48468 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 24 ms 48444 KB Output is correct
9 Correct 23 ms 47372 KB Output is correct
10 Correct 22 ms 47412 KB Output is correct
11 Correct 287 ms 63724 KB Output is correct
12 Correct 768 ms 72296 KB Output is correct
13 Correct 1109 ms 83260 KB Output is correct
14 Correct 773 ms 87300 KB Output is correct
15 Correct 751 ms 87392 KB Output is correct
16 Correct 689 ms 84432 KB Output is correct
17 Correct 966 ms 82716 KB Output is correct
18 Correct 916 ms 76676 KB Output is correct
19 Correct 964 ms 78516 KB Output is correct
20 Correct 472 ms 85572 KB Output is correct
21 Incorrect 26 ms 48488 KB Output isn't correct
22 Halted 0 ms 0 KB -