oj.uz

Submission #364008

# Submission time Handle Problem Language Result Execution time Memory
364008 2021-02-08T02:05:06 Z mario05092929 Parachute rings (IOI12_rings) C++11
0 / 100
 518 ms 53248 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,ind[1000005];
int ans,mx,c[1000005],c2[1000005];
int cnt[1000005],par[1000005];
int p[1000005],made[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; made[x] |= made[y]; return true;
}

void Cycle(int x,int pr) {
	if(c2[x]) {
		if(++cnt[x] == mx) ans++;
		for(int i = par[x];i^x;i = par[i]) {
			if(++cnt[i] == mx) ans++;
		}
		return;
	}
	if(c[x]) return;
	c[x] = c2[x] = 1;
	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)&&!made[Find(x)]) {
		mx++; ans = 0;
		Cycle(x,-1);
		made[Find(x)] = 1;
	}
}

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 19 ms 23916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 31.0

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