oj.uz

Submission #538319

# Submission time Handle Problem Language Result Execution time Memory
538319 2022-03-16T15:20:17 Z mario05092929 Parachute rings (IOI12_rings) C++17
0 / 100
 357 ms 50952 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const long long INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,Q,fl,ind[1000005];
int ans,mx,c[1000005],c2[1000005];
int cnt[1000005],par[1000005];
int p[1000005];
vec v[1000005];

int Find(int x) {return (x^p[x] ? p[x] = Find(p[x]) : x);}

void Ind3(int x) {
    mx++;
    ans = 0;
    if(++cnt[x] == mx) ans++;
    for(int i : v[x]) {
        if(++cnt[i] == mx) ans++;
    }
}

void Ind4(int x) {
    mx++;
    ans = 0;
    if(++cnt[x] == mx) ans++;
}

bool merge(int x,int y) {
    x = Find(x), y = Find(y);
    if(x == y) return false;
    p[y] = x; return true;
}

vec g;
bool canCycle;

void Cycle(int x,int pr) {
    if(c2[x]) {
        canCycle = 1;
        if(++cnt[x] == mx) ans++;
        for(int i = par[x];i^x;i = par[i]) {
            if(++cnt[i] == mx) ans++;
        }
        return;
    }
    if(c[x]) {g.pb(x); return;}
    c[x] = c2[x] = 1;
    g.pb(x);
    for(int i : v[x]) if(i != pr) par[x] = i, Cycle(i,x);
    c2[x] = 0;
}

void update(int x,int y) {
    v[x].pb(y), v[y].pb(x);
    ind[x]++, ind[y]++;
    if(ind[x] == 3) Ind3(x);
    if(ind[y] == 3) Ind3(y);
    if(ind[x] == 4) Ind4(x);
    if(ind[y] == 4) Ind4(y);
    if(!merge(x,y)) {
        g.clear();
        canCycle = 0;
        if(c[x]) swap(x,y);
        mx++; ans = 0;
        Cycle(x,-1);
        if(!canCycle) {
            //if(g.size() > 2) exit(-1);
            //if(g.size() < 2) return;
            for(int i : g) if(++cnt[i] == mx) ans++;
            
        }
    }
}

void Init(int n_) {
    n = n_;
    for(int i = 1;i <= n;i++) p[i] = i;
}

void Link(int A,int B) {
    update(A+1,B+1);
}

int CountCritical() {
    return ans;
}

Compilation message

rings.cpp:6: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
rings.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
rings.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      |

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 50952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -