oj.uz

Submission #1017956

# Submission time Handle Problem Language Result Execution time Memory
1017956 2024-07-09T11:53:03 Z pcc Parachute rings (IOI12_rings) C++17
52 / 100
 4000 ms 48348 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 14680 KB Output is correct
2 Correct 208 ms 11632 KB Output is correct
3 Correct 219 ms 12116 KB Output is correct
4 Correct 9 ms 10588 KB Output is correct
5 Correct 22 ms 10844 KB Output is correct
6 Correct 37 ms 11084 KB Output is correct
7 Correct 26 ms 11096 KB Output is correct
8 Correct 44 ms 10844 KB Output is correct
9 Correct 211 ms 12116 KB Output is correct
10 Correct 216 ms 12128 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 208 ms 11632 KB Output is correct
3 Correct 219 ms 12116 KB Output is correct
4 Correct 9 ms 10588 KB Output is correct
5 Correct 22 ms 10844 KB Output is correct
6 Correct 37 ms 11084 KB Output is correct
7 Correct 26 ms 11096 KB Output is correct
8 Correct 44 ms 10844 KB Output is correct
9 Correct 211 ms 12116 KB Output is correct
10 Correct 216 ms 12128 KB Output is correct
11 Correct 216 ms 2068 KB Output is correct
12 Correct 446 ms 3572 KB Output is correct
13 Correct 422 ms 3796 KB Output is correct
14 Correct 295 ms 2944 KB Output is correct
15 Correct 241 ms 4180 KB Output is correct
16 Correct 72 ms 1360 KB Output is correct
17 Correct 452 ms 3668 KB Output is correct
18 Correct 434 ms 5088 KB Output is correct
19 Correct 110 ms 1364 KB Output is correct
20 Correct 420 ms 3796 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 208 ms 11632 KB Output is correct
3 Correct 219 ms 12116 KB Output is correct
4 Correct 9 ms 10588 KB Output is correct
5 Correct 22 ms 10844 KB Output is correct
6 Correct 37 ms 11084 KB Output is correct
7 Correct 26 ms 11096 KB Output is correct
8 Correct 44 ms 10844 KB Output is correct
9 Correct 211 ms 12116 KB Output is correct
10 Correct 216 ms 12128 KB Output is correct
11 Correct 216 ms 2068 KB Output is correct
12 Correct 446 ms 3572 KB Output is correct
13 Correct 422 ms 3796 KB Output is correct
14 Correct 295 ms 2944 KB Output is correct
15 Correct 241 ms 4180 KB Output is correct
16 Correct 72 ms 1360 KB Output is correct
17 Correct 452 ms 3668 KB Output is correct
18 Correct 434 ms 5088 KB Output is correct
19 Correct 110 ms 1364 KB Output is correct
20 Correct 420 ms 3796 KB Output is correct
21 Correct 277 ms 4236 KB Output is correct
22 Correct 428 ms 6144 KB Output is correct
23 Correct 543 ms 7636 KB Output is correct
24 Correct 2640 ms 23512 KB Output is correct
25 Correct 505 ms 15952 KB Output is correct
26 Correct 3046 ms 26076 KB Output is correct
27 Correct 670 ms 8280 KB Output is correct
28 Correct 3953 ms 29264 KB Output is correct
29 Correct 1562 ms 21208 KB Output is correct
30 Correct 805 ms 9288 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 208 ms 11632 KB Output is correct
3 Correct 219 ms 12116 KB Output is correct
4 Correct 9 ms 10588 KB Output is correct
5 Correct 22 ms 10844 KB Output is correct
6 Correct 37 ms 11084 KB Output is correct
7 Correct 26 ms 11096 KB Output is correct
8 Correct 44 ms 10844 KB Output is correct
9 Correct 211 ms 12116 KB Output is correct
10 Correct 216 ms 12128 KB Output is correct
11 Execution timed out 4014 ms 48348 KB Time limit exceeded
12 Halted 0 ms 0 KB -