oj.uz

Submission #1017958

# Submission time Handle Problem Language Result Execution time Memory
1017958 2024-07-09T11:54:02 Z pcc Parachute rings (IOI12_rings) C++17
100 / 100
 999 ms 161400 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 1e6+10;

int phase;
int N;
bool initflag = false;

struct DSU{
	int cnt[mxn][4];//deg = 0,deg = 1,deg = 2,deg>2
	int dsu[mxn],sz[mxn],deg[mxn];
	int good,cycle;
	int WA = false;
	void init(int n){
		good = true;
		cycle = -1;
		for(int i = 0;i<n;i++){
			dsu[i] = i,sz[i] = 1;
			memset(cnt[i],0,sizeof(cnt[i]));
			cnt[i][0] = 1;
		}
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void check(int a){
		a = root(a);
		if(cnt[a][3])good = false,cycle = -1;
		else if(!cnt[a][1]&&cycle != -1)WA = true;
		else if(!cnt[a][1])cycle = a;
		return;
	}
	void del(int k){
		int r = root(k);
		cnt[r][min(deg[k],3)]--;
		return;
	}
	void add(int k){
		int r = root(k);
		cnt[r][min(deg[k],3)]++;
		return;
	}
	void add_edge(int a,int b){
		del(a);deg[a]++;add(a);
		del(b);deg[b]++;add(b);
		a = root(a),b = root(b);
		if(a != b){
			if(sz[a]<sz[b])swap(a,b);
			dsu[b] = a;
			sz[a] += sz[b];
			for(int i = 0;i<4;i++)cnt[a][i] += cnt[b][i];
		}
		check(a);
		return;
	}
};

vector<pii> edges;


namespace PHASE1{
	DSU dsu;
	void INIT(){
		//cerr<<"PHASE 1 init!"<<endl;
		dsu.init(N);
		//cerr<<"PHASE 1 INIT DONE!"<<endl;
	}
	void ADD(int a,int b){
		//cerr<<"PHASE 1 add: "<<a<<','<<b<<endl;
		dsu.add_edge(a,b);
		if(!dsu.good){
			phase = 2;
			initflag = true;
		}
		//cerr<<"PHASE 1 add done!"<<endl;
		return;
	}
	int CALC(){
		//cerr<<"PHASE 1 CALC"<<endl;
		if(dsu.WA)return 0;
		if(dsu.cycle != -1)return dsu.sz[dsu.root(dsu.cycle)];
		else return N;
	}
}

namespace PHASE2{
	struct GRAPH{
		DSU dsu;
		int ban;
		GRAPH(int k = -1){
			ban = k;
			dsu.init(N);
		}
		void add_edge(int a,int b){
			if(a == ban||b == ban)return;
			dsu.add_edge(a,b);
			//cerr<<"ADD_EDGE: "<<ban<<','<<a<<' '<<b<<':'<<dsu.cycle<<endl;
			return;
		}
		bool isgood(){
			return dsu.good&&dsu.cycle == -1;
		}
	};

	GRAPH v[5];
	int ptr = 0;
	void INIT(){
		//cerr<<"PHASE 2 INIT!"<<endl;
		//cerr<<"PHASE 2 INIT!"<<endl;
		int fat = -1;
		ptr = 0;
		for(int i = 0;i<N;i++)if(PHASE1::dsu.deg[i] >= 3)fat = i;
		assert(fat != -1);
		v[ptr++].ban = fat;
		for(auto &i:edges){
			if(i.fs == fat)v[ptr++].ban = i.sc;
			if(i.sc == fat)v[ptr++].ban = i.fs;
		}
		for(int i = 0;i<ptr;i++)v[i].dsu.init(N);
		//cerr<<"SPECIALS: ";for(int i = 0;i<ptr;i++)cerr<<v[i].ban<<' '<<v[i].dsu.cycle<<',';cerr<<endl;
		for(auto &i:edges){
			for(int j = 0;j<ptr;j++)v[j].add_edge(i.fs,i.sc);
		}
		//cerr<<"SPECIALS: ";for(int i = 0;i<ptr;i++)cerr<<v[i].ban<<' '<<v[i].dsu.cycle<<',';cerr<<endl;
		//cerr<<"PHASE 2 INIT DONE!"<<endl;
	}
	void ADD(int a,int b){
		//cerr<<"PHASE 2 ADD: "<<a<<','<<b<<endl;
		for(int i = 0;i<ptr;i++)v[i].add_edge(a,b);
		//cerr<<"PHASE 2 ADD DONE!"<<endl;
		return;
	}
	int CALC(){
		//cerr<<"PHASE 2 CALC"<<endl;
		if(PHASE1::dsu.WA)return 0;
		int ans = 0;
		for(int i = 0;i<ptr;i++)ans += v[i].isgood();
		return ans;
	}
}

void Init(int N_) {
	edges.clear();
	phase = 1;
	N = N_;
	PHASE1::INIT();
}

void Link(int A, int B) {
	edges.push_back(pii(A,B));
	if(phase == 1)PHASE1::ADD(A,B);
	else PHASE2::ADD(A,B);
	if(initflag){
		//cerr<<"PHASE 2 INIT!"<<endl;
		PHASE2::INIT();
		initflag = false;
	}
	return;
}

int CountCritical() {
	if(phase == 1)return PHASE1::CALC();
	else return PHASE2::CALC();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 3 ms 15192 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 15196 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 17392 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 29644 KB Output is correct
2 Correct 772 ms 133652 KB Output is correct
3 Correct 915 ms 160180 KB Output is correct
4 Correct 317 ms 58804 KB Output is correct
5 Correct 318 ms 58804 KB Output is correct
6 Correct 301 ms 58128 KB Output is correct
7 Correct 903 ms 159412 KB Output is correct
8 Correct 983 ms 153144 KB Output is correct
9 Correct 999 ms 161400 KB Output is correct
10 Correct 274 ms 57528 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 3 ms 15192 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 15196 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 17392 KB Output is correct
11 Correct 3 ms 15192 KB Output is correct
12 Correct 4 ms 15708 KB Output is correct
13 Correct 4 ms 15708 KB Output is correct
14 Correct 4 ms 15708 KB Output is correct
15 Correct 4 ms 16476 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 5 ms 17756 KB Output is correct
18 Correct 6 ms 16600 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 4 ms 15708 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 3 ms 15192 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 15196 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 17392 KB Output is correct
11 Correct 3 ms 15192 KB Output is correct
12 Correct 4 ms 15708 KB Output is correct
13 Correct 4 ms 15708 KB Output is correct
14 Correct 4 ms 15708 KB Output is correct
15 Correct 4 ms 16476 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 5 ms 17756 KB Output is correct
18 Correct 6 ms 16600 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 4 ms 15708 KB Output is correct
21 Correct 9 ms 15708 KB Output is correct
22 Correct 14 ms 17884 KB Output is correct
23 Correct 17 ms 16864 KB Output is correct
24 Correct 32 ms 25568 KB Output is correct
25 Correct 12 ms 25692 KB Output is correct
26 Correct 28 ms 24800 KB Output is correct
27 Correct 18 ms 17112 KB Output is correct
28 Correct 36 ms 24532 KB Output is correct
29 Correct 26 ms 25316 KB Output is correct
30 Correct 20 ms 17112 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 3 ms 15192 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 15196 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 17392 KB Output is correct
11 Correct 121 ms 29644 KB Output is correct
12 Correct 772 ms 133652 KB Output is correct
13 Correct 915 ms 160180 KB Output is correct
14 Correct 317 ms 58804 KB Output is correct
15 Correct 318 ms 58804 KB Output is correct
16 Correct 301 ms 58128 KB Output is correct
17 Correct 903 ms 159412 KB Output is correct
18 Correct 983 ms 153144 KB Output is correct
19 Correct 999 ms 161400 KB Output is correct
20 Correct 274 ms 57528 KB Output is correct
21 Correct 3 ms 15192 KB Output is correct
22 Correct 4 ms 15708 KB Output is correct
23 Correct 4 ms 15708 KB Output is correct
24 Correct 4 ms 15708 KB Output is correct
25 Correct 4 ms 16476 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 5 ms 17756 KB Output is correct
28 Correct 6 ms 16600 KB Output is correct
29 Correct 3 ms 14940 KB Output is correct
30 Correct 4 ms 15708 KB Output is correct
31 Correct 9 ms 15708 KB Output is correct
32 Correct 14 ms 17884 KB Output is correct
33 Correct 17 ms 16864 KB Output is correct
34 Correct 32 ms 25568 KB Output is correct
35 Correct 12 ms 25692 KB Output is correct
36 Correct 28 ms 24800 KB Output is correct
37 Correct 18 ms 17112 KB Output is correct
38 Correct 36 ms 24532 KB Output is correct
39 Correct 26 ms 25316 KB Output is correct
40 Correct 20 ms 17112 KB Output is correct
41 Correct 89 ms 32104 KB Output is correct
42 Correct 451 ms 134084 KB Output is correct
43 Correct 178 ms 134356 KB Output is correct
44 Correct 712 ms 151216 KB Output is correct
45 Correct 669 ms 156228 KB Output is correct
46 Correct 269 ms 52768 KB Output is correct
47 Correct 236 ms 53260 KB Output is correct
48 Correct 408 ms 151056 KB Output is correct
49 Correct 247 ms 55724 KB Output is correct
50 Correct 273 ms 55216 KB Output is correct
51 Correct 209 ms 121036 KB Output is correct
52 Correct 573 ms 125020 KB Output is correct
53 Correct 423 ms 150300 KB Output is correct
54 Correct 772 ms 135116 KB Output is correct
55 Correct 992 ms 145560 KB Output is correct