oj.uz

Submission #658093

# Submission time Handle Problem Language Result Execution time Memory
658093 2022-11-12T07:24:56 Z jiahng Parachute rings (IOI12_rings) C++14
38 / 100
 4000 ms 195480 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
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;
unordered_set <int> st[maxn];
int d[maxn];
int maxD;
unordered_set <int> adj[maxn];
 
vpi all_edges;
int p[6][maxn];
int edges[6][maxn], sz[6][maxn];
unordered_set <int> cycles[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){
    edges[i][fl(i,B)]++;
    if (fl(i, A) != fl(i,B)){
        int pA = fl(i,A), pB = fl(i,B);
        sz[i][pB] += sz[i][pA];
        edges[i][pB] += edges[i][pA];
        if (cycles[i].find(pA) != cycles[i].end()) cycles[i].erase(pA);
        p[i][pA] = pB;
    }
    if (edges[i][fl(i,B)] >= sz[i][fl(i,B)]) cycles[i].insert(fl(i,B));
}
int bigx;
multiset <int> degrees;
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, edges[i][j] = 0;
    FOR(i,0,N-1){
        adj[i].clear(); st[i].clear();
    }
    FOR(i,0,5) cycles[i].clear();
    degrees.clear();
    FOR(i,0,N-1) d[i] = 0;
    FOR(i,0,N-1) st[0].insert(i);
    FOR(i,0,N-1) degrees.insert(0);
    all_edges.clear();
    bigx = -1;
}
void Link(int A, int B) {
    assert(st[d[A]].count(A) && st[d[B]].count(B) && degrees.count(d[A]) && degrees.count(d[B]));
    st[d[A]].erase(A); st[d[B]].erase(B);
    degrees.erase(degrees.find(d[A])); degrees.erase(degrees.find(d[B]));
    d[A]++; d[B]++;
    st[d[A]].insert(A); st[d[B]].insert(B);
    degrees.insert(d[A]); degrees.insert(d[B]);
 
    //assert(!adj[A].count(B) && !adj[B].count(A));
    adj[A].insert(B); adj[B].insert(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;
        aFOR(i, all_edges) if (i.f != bigx && i.s != bigx) add(4,i.f,i.s);
    }
    
    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);
    if (bigx != -1 && A != bigx && B != bigx) add(4, A, B);
}
 
int CountCritical() {
    if (N == 1) return 1;
    assert(degrees.size() == N);
    if (maxD >= 4){
        if (*(--(--degrees.end())) >= 4) return 0;
        if (st[maxD].size() == 1){
            int x = *st[maxD].begin();
            bool no = 0;
            if (!cycles[4].empty()) no = 1;
            aFOR(i, st[3]) if (!adj[x].count(i)) no = 1;
            if (no) 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,N-1){
            cout << "ADJ " << i << ": ";
            aFOR(j, adj[i]) cout << j << ' ';
            cout << '\n';
        }
        cout << "POS: ";
        aFOR(i, pos) cout << i << ' ';
        cout << '\n';
        */
        FOR(i,0,pos.size()-1){
            bool no = 0;
            aFOR(j, st[3]) if (pos[i] != j && !adj[pos[i]].count(j)){
                //cout << "NO " << pos[i] << ' ' << j << '\n';
                no = 1; break;
            }
            if (no) continue;
            if (cycles[i].empty()){
                //cout << "! " << i << '\n';
                ans++;
            }
        }
        return ans;
    }else{
        if (cycles[5].size() == 0) return N;
        else if (cycles[5].size() == 1) return sz[5][fl(5,*cycles[5].begin())];
        else return 0;
    }
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from rings.cpp:1:
rings.cpp: In function 'int CountCritical()':
rings.cpp:113:27: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |     assert(degrees.size() == N);
      |            ~~~~~~~~~~~~~~~^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110028 KB Output is correct
2 Correct 141 ms 111500 KB Output is correct
3 Correct 160 ms 111816 KB Output is correct
4 Correct 65 ms 110280 KB Output is correct
5 Correct 97 ms 111048 KB Output is correct
6 Correct 164 ms 111792 KB Output is correct
7 Correct 82 ms 110988 KB Output is correct
8 Correct 112 ms 111472 KB Output is correct
9 Correct 179 ms 111796 KB Output is correct
10 Correct 163 ms 111848 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4075 ms 195480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110028 KB Output is correct
2 Correct 141 ms 111500 KB Output is correct
3 Correct 160 ms 111816 KB Output is correct
4 Correct 65 ms 110280 KB Output is correct
5 Correct 97 ms 111048 KB Output is correct
6 Correct 164 ms 111792 KB Output is correct
7 Correct 82 ms 110988 KB Output is correct
8 Correct 112 ms 111472 KB Output is correct
9 Correct 179 ms 111796 KB Output is correct
10 Correct 163 ms 111848 KB Output is correct
11 Correct 130 ms 111820 KB Output is correct
12 Correct 329 ms 113536 KB Output is correct
13 Correct 337 ms 113604 KB Output is correct
14 Correct 322 ms 113060 KB Output is correct
15 Correct 424 ms 114508 KB Output is correct
16 Correct 307 ms 113480 KB Output is correct
17 Correct 320 ms 113512 KB Output is correct
18 Correct 1109 ms 115504 KB Output is correct
19 Correct 481 ms 113532 KB Output is correct
20 Correct 477 ms 113616 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110028 KB Output is correct
2 Correct 141 ms 111500 KB Output is correct
3 Correct 160 ms 111816 KB Output is correct
4 Correct 65 ms 110280 KB Output is correct
5 Correct 97 ms 111048 KB Output is correct
6 Correct 164 ms 111792 KB Output is correct
7 Correct 82 ms 110988 KB Output is correct
8 Correct 112 ms 111472 KB Output is correct
9 Correct 179 ms 111796 KB Output is correct
10 Correct 163 ms 111848 KB Output is correct
11 Correct 130 ms 111820 KB Output is correct
12 Correct 329 ms 113536 KB Output is correct
13 Correct 337 ms 113604 KB Output is correct
14 Correct 322 ms 113060 KB Output is correct
15 Correct 424 ms 114508 KB Output is correct
16 Correct 307 ms 113480 KB Output is correct
17 Correct 320 ms 113512 KB Output is correct
18 Correct 1109 ms 115504 KB Output is correct
19 Correct 481 ms 113532 KB Output is correct
20 Correct 477 ms 113616 KB Output is correct
21 Execution timed out 4056 ms 122504 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110028 KB Output is correct
2 Correct 141 ms 111500 KB Output is correct
3 Correct 160 ms 111816 KB Output is correct
4 Correct 65 ms 110280 KB Output is correct
5 Correct 97 ms 111048 KB Output is correct
6 Correct 164 ms 111792 KB Output is correct
7 Correct 82 ms 110988 KB Output is correct
8 Correct 112 ms 111472 KB Output is correct
9 Correct 179 ms 111796 KB Output is correct
10 Correct 163 ms 111848 KB Output is correct
11 Execution timed out 4075 ms 195480 KB Time limit exceeded
12 Halted 0 ms 0 KB -