oj.uz

Submission #658120

# Submission time Handle Problem Language Result Execution time Memory
658120 2022-11-12T08:03:30 Z jiahng Parachute rings (IOI12_rings) C++14
55 / 100
 2100 ms 171280 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
 
typedef long long ll;
#define ll int
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 1000010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N;
int d[maxn], maxD;
vi st[maxn], adj[maxn],cycles[6];
vpi all_edges;
int p[6][maxn], edges[6][maxn], sz[6][maxn], ncycles[6];
vi pos;
int fl(int i, int x){
    if (p[i][x] == x) return x;
    return p[i][x] = fl(i, p[i][x]);
}
 
void add(int i, int A, int B){
    if (sz[fl(i,A)] > sz[fl(i,B)]) swap(A,B);
    
    if (fl(i, A) != fl(i,B)){
        int pA = fl(i,A), pB = fl(i,B);
        if (edges[i][pA] >= sz[i][pA]) ncycles[i]--;
        if (edges[i][pB] >= sz[i][pB]) ncycles[i]--;
        sz[i][pB] += sz[i][pA];
        edges[i][pB] += edges[i][pA];
        p[i][pA] = pB;
    }else if (edges[i][fl(i,A)] >= sz[i][fl(i,A)]) ncycles[i]--;
    edges[i][fl(i,B)]++;
    if (edges[i][fl(i,B)] >= sz[i][fl(i,B)]){
        ncycles[i]++; cycles[i].pb(fl(i,B));
    }
}
int bigx;
int gt3 = 0;

void Init(int N_) {
    N = N_;
    maxD = 0;
    FOR(i,0,5) FOR(j,0,N-1) p[i][j] = j,sz[i][j] = 1;
    bigx = -1;
}
void Link(int A, int B) {
    if (d[A] == 3) gt3++;
    if (d[B] == 3) gt3++;
    d[A]++; d[B]++;
    st[d[A]].pb(A); st[d[B]].pb(B);
 
    adj[A].pb(B); adj[B].pb(A);
 
    if (pos.empty() && (d[A] == 3 || d[B] == 3)){
        if (d[A] == 3){
            aFOR(i, adj[A]) pos.pb(i);
            pos.pb(A);
        }else if (d[B] == 3){
            pos.pb(B); aFOR(i, adj[B]) pos.pb(i);
        }
        FOR(i,0,pos.size()-1){
            aFOR(j, all_edges) if (j.f != pos[i] && j.s != pos[i]) add(i,j.f,j.s);
        }
    }
    
    if (bigx == -1 && (d[A] >= 4 || d[B] >= 4)){
        if (d[A] >= 4) bigx = A;
        else if (d[B] >= 4) bigx = B;
    }
    
    all_edges.pb(pi(A,B));
    maxD = max({maxD, d[A], d[B]});
 
    add(5,A,B);
    FOR(i,0,(int)pos.size()-1) if (A != pos[i] && B != pos[i]) add(i,A,B);
}
 
int CountCritical() {
    if (N == 1) return 1;
    if (maxD >= 4){
        if (gt3 > 1) return 0;
        if (st[maxD].size() == 1){
            int x = *st[maxD].begin();
            bool no = 0;
            if (find(all(pos),x) == pos.end()) return 0;
            int i = find(all(pos), x) - pos.begin();
            if (!cycles[i].empty()) no = 1;
            aFOR(i, st[3]) if (i != x && find(all(adj[i]), x) == adj[i].end()) return 0;
            return 1;
        }else return 0;
    }else if (maxD <= 1) return N;
    else if (maxD == 3){
        if (st[3].size() > 4) return 0;
       
        int ans = 0;
        FOR(i,0,pos.size()-1){
            bool no = 0;
            aFOR(j, st[3]) if (pos[i] != j && find(all(adj[j]), pos[i]) == adj[j].end()){
                no = 1; break;
            }
            if (no) continue;
            if (cycles[i].empty()){
                //cout << "! " << i << '\n';
                ans++;
            }
        }
        return ans;
    }else{
        if (ncycles[5] == 0) return N;
        else if (ncycles[5] == 1) return sz[5][fl(5,cycles[5][0])];
        else return 0;
    }
}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:105:18: warning: variable 'no' set but not used [-Wunused-but-set-variable]
  105 |             bool no = 0;
      |                  ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47312 KB Output is correct
2 Correct 24 ms 47868 KB Output is correct
3 Correct 30 ms 48096 KB Output is correct
4 Correct 24 ms 47484 KB Output is correct
5 Correct 31 ms 47700 KB Output is correct
6 Correct 26 ms 47984 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 25 ms 47744 KB Output is correct
9 Correct 30 ms 47984 KB Output is correct
10 Correct 29 ms 48084 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 100032 KB Output is correct
2 Correct 1714 ms 142392 KB Output is correct
3 Correct 2049 ms 171280 KB Output is correct
4 Correct 1294 ms 148860 KB Output is correct
5 Correct 1266 ms 148956 KB Output is correct
6 Correct 1225 ms 147380 KB Output is correct
7 Correct 2041 ms 170212 KB Output is correct
8 Correct 1837 ms 157240 KB Output is correct
9 Correct 1964 ms 164508 KB Output is correct
10 Correct 909 ms 142740 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47312 KB Output is correct
2 Correct 24 ms 47868 KB Output is correct
3 Correct 30 ms 48096 KB Output is correct
4 Correct 24 ms 47484 KB Output is correct
5 Correct 31 ms 47700 KB Output is correct
6 Correct 26 ms 47984 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 25 ms 47744 KB Output is correct
9 Correct 30 ms 47984 KB Output is correct
10 Correct 29 ms 48084 KB Output is correct
11 Correct 27 ms 47956 KB Output is correct
12 Correct 29 ms 48596 KB Output is correct
13 Correct 30 ms 48596 KB Output is correct
14 Correct 29 ms 48472 KB Output is correct
15 Correct 30 ms 49296 KB Output is correct
16 Correct 28 ms 48388 KB Output is correct
17 Correct 29 ms 48844 KB Output is correct
18 Correct 30 ms 49444 KB Output is correct
19 Correct 28 ms 48520 KB Output is correct
20 Correct 29 ms 48740 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47312 KB Output is correct
2 Correct 24 ms 47868 KB Output is correct
3 Correct 30 ms 48096 KB Output is correct
4 Correct 24 ms 47484 KB Output is correct
5 Correct 31 ms 47700 KB Output is correct
6 Correct 26 ms 47984 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 25 ms 47744 KB Output is correct
9 Correct 30 ms 47984 KB Output is correct
10 Correct 29 ms 48084 KB Output is correct
11 Correct 27 ms 47956 KB Output is correct
12 Correct 29 ms 48596 KB Output is correct
13 Correct 30 ms 48596 KB Output is correct
14 Correct 29 ms 48472 KB Output is correct
15 Correct 30 ms 49296 KB Output is correct
16 Correct 28 ms 48388 KB Output is correct
17 Correct 29 ms 48844 KB Output is correct
18 Correct 30 ms 49444 KB Output is correct
19 Correct 28 ms 48520 KB Output is correct
20 Correct 29 ms 48740 KB Output is correct
21 Correct 42 ms 51516 KB Output is correct
22 Correct 53 ms 54012 KB Output is correct
23 Correct 65 ms 55692 KB Output is correct
24 Correct 2100 ms 57500 KB Output is correct
25 Correct 465 ms 54912 KB Output is correct
26 Incorrect 82 ms 55996 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47312 KB Output is correct
2 Correct 24 ms 47868 KB Output is correct
3 Correct 30 ms 48096 KB Output is correct
4 Correct 24 ms 47484 KB Output is correct
5 Correct 31 ms 47700 KB Output is correct
6 Correct 26 ms 47984 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 25 ms 47744 KB Output is correct
9 Correct 30 ms 47984 KB Output is correct
10 Correct 29 ms 48084 KB Output is correct
11 Correct 529 ms 100032 KB Output is correct
12 Correct 1714 ms 142392 KB Output is correct
13 Correct 2049 ms 171280 KB Output is correct
14 Correct 1294 ms 148860 KB Output is correct
15 Correct 1266 ms 148956 KB Output is correct
16 Correct 1225 ms 147380 KB Output is correct
17 Correct 2041 ms 170212 KB Output is correct
18 Correct 1837 ms 157240 KB Output is correct
19 Correct 1964 ms 164508 KB Output is correct
20 Correct 909 ms 142740 KB Output is correct
21 Correct 27 ms 47956 KB Output is correct
22 Correct 29 ms 48596 KB Output is correct
23 Correct 30 ms 48596 KB Output is correct
24 Correct 29 ms 48472 KB Output is correct
25 Correct 30 ms 49296 KB Output is correct
26 Correct 28 ms 48388 KB Output is correct
27 Correct 29 ms 48844 KB Output is correct
28 Correct 30 ms 49444 KB Output is correct
29 Correct 28 ms 48520 KB Output is correct
30 Correct 29 ms 48740 KB Output is correct
31 Correct 42 ms 51516 KB Output is correct
32 Correct 53 ms 54012 KB Output is correct
33 Correct 65 ms 55692 KB Output is correct
34 Correct 2100 ms 57500 KB Output is correct
35 Correct 465 ms 54912 KB Output is correct
36 Incorrect 82 ms 55996 KB Output isn't correct
37 Halted 0 ms 0 KB -