Submission #513835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
513835	2022-01-17T16:59:53 Z	fatemetmhr	Meetings (JOI19_meetings)	C++17	29 / 100	1805 ms	12488 KB

meetings

//  ~Be name khoda~  //

#include "meetings.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int n;
vector <int> adj[maxn5], tmp, av;
int mx[maxn5], sz[maxn5];
bool rem[maxn5], mark[maxn5];
int lev = 0;

inline void remo(int a, int b){
	tmp.clear();
	for(auto u : adj[a]) 
		if(u != b) tmp.pb(u);
	adj[a].clear();
	for(auto u : tmp)
		adj[a].pb(u);
	return;
}

inline void dfs(int v, int par){
	sz[v] = 1;
	mx[v] = 0;
	av.pb(v);
	for(auto u : adj[v]) if(u != par && !rem[u]){
		dfs(u, v);
		mx[v] = max(mx[v], sz[u]);
		sz[v] += sz[u];
	}
	return;
}


inline void add(int r, int v){
	lev++;
	//cout << "adding " << r << ' ' << v << endl;
	av.clear();
	dfs(r, -1);
	int c = r;
	for(auto u : av)
		if(max(mx[u], int(av.size()) - sz[u]) < max(mx[c], int(av.size()) - sz[c]))
			c = u;
	int sub = -1;
	//cout << "centroid " << c << endl;
	assert(lev <= 11);
	for(auto uu : adj[c]) if(!rem[uu]){
		int u = uu;
		int t = Query(c, u, v);
		if(t == v){
			//cout << "right " << u << endl;
			remo(u, c);
			remo(c, u);
			adj[u].pb(v);
			adj[c].pb(v);
			adj[v].pb(u);
			adj[v].pb(c);
			return;
		}
		else if(t == u){
			sub = u;
			break;
		}
		else if(t != c){
			remo(u, c);
			remo(c, u);
			adj[u].pb(t);
			adj[v].pb(t);
			adj[c].pb(t);
			adj[t].pb(u);
			adj[t].pb(c);
			adj[t].pb(v);
			mark[t] = true;
			return;
		}
	}
	//cout << "ok " << sub << endl;
	if(sub != -1){
		rem[c] = true;
		add(sub, v);
		return;
	}
	adj[c].pb(v);
	adj[v].pb(c);
}

void Solve(int nn){
	n = nn;
	for(int i = 1; i < n; i++) if(!mark[i]){
		fill(rem, rem + n + 5, false);
		lev = 0;
		add(0, i);
		mark[i] = true;
	}
	for(int i = 0; i < n; i++) for(auto u : adj[i]){
		//cout << "edge " << i << ' '<< u << endl;
		if(i < u) Bridge(i, u);
	}
	return;
}

/*
5
0 4
2 4
2 3
1 4
*/

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	12104 KB	Output is correct
2	Correct	9 ms	12104 KB	Output is correct
3	Correct	8 ms	12104 KB	Output is correct
4	Correct	7 ms	11976 KB	Output is correct
5	Correct	7 ms	12104 KB	Output is correct
6	Correct	7 ms	12008 KB	Output is correct
7	Correct	6 ms	12104 KB	Output is correct
8	Correct	7 ms	12104 KB	Output is correct
9	Correct	7 ms	12104 KB	Output is correct
10	Correct	8 ms	12104 KB	Output is correct
11	Correct	7 ms	12020 KB	Output is correct
12	Correct	9 ms	12104 KB	Output is correct
13	Correct	10 ms	12104 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	12104 KB	Output is correct
2	Correct	9 ms	12104 KB	Output is correct
3	Correct	8 ms	12104 KB	Output is correct
4	Correct	7 ms	11976 KB	Output is correct
5	Correct	7 ms	12104 KB	Output is correct
6	Correct	7 ms	12008 KB	Output is correct
7	Correct	6 ms	12104 KB	Output is correct
8	Correct	7 ms	12104 KB	Output is correct
9	Correct	7 ms	12104 KB	Output is correct
10	Correct	8 ms	12104 KB	Output is correct
11	Correct	7 ms	12020 KB	Output is correct
12	Correct	9 ms	12104 KB	Output is correct
13	Correct	10 ms	12104 KB	Output is correct
14	Correct	10 ms	12104 KB	Output is correct
15	Correct	9 ms	12028 KB	Output is correct
16	Correct	8 ms	12104 KB	Output is correct
17	Correct	6 ms	12116 KB	Output is correct
18	Correct	8 ms	12104 KB	Output is correct
19	Correct	7 ms	12108 KB	Output is correct
20	Correct	8 ms	12104 KB	Output is correct
21	Correct	8 ms	12104 KB	Output is correct
22	Correct	7 ms	12104 KB	Output is correct
23	Correct	9 ms	12120 KB	Output is correct
24	Correct	9 ms	12112 KB	Output is correct
25	Correct	8 ms	12104 KB	Output is correct
26	Correct	7 ms	12104 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	12104 KB	Output is correct
2	Correct	9 ms	12104 KB	Output is correct
3	Correct	8 ms	12104 KB	Output is correct
4	Correct	7 ms	11976 KB	Output is correct
5	Correct	7 ms	12104 KB	Output is correct
6	Correct	7 ms	12008 KB	Output is correct
7	Correct	6 ms	12104 KB	Output is correct
8	Correct	7 ms	12104 KB	Output is correct
9	Correct	7 ms	12104 KB	Output is correct
10	Correct	8 ms	12104 KB	Output is correct
11	Correct	7 ms	12020 KB	Output is correct
12	Correct	9 ms	12104 KB	Output is correct
13	Correct	10 ms	12104 KB	Output is correct
14	Correct	10 ms	12104 KB	Output is correct
15	Correct	9 ms	12028 KB	Output is correct
16	Correct	8 ms	12104 KB	Output is correct
17	Correct	6 ms	12116 KB	Output is correct
18	Correct	8 ms	12104 KB	Output is correct
19	Correct	7 ms	12108 KB	Output is correct
20	Correct	8 ms	12104 KB	Output is correct
21	Correct	8 ms	12104 KB	Output is correct
22	Correct	7 ms	12104 KB	Output is correct
23	Correct	9 ms	12120 KB	Output is correct
24	Correct	9 ms	12112 KB	Output is correct
25	Correct	8 ms	12104 KB	Output is correct
26	Correct	7 ms	12104 KB	Output is correct
27	Correct	13 ms	12104 KB	Output is correct
28	Correct	13 ms	12164 KB	Output is correct
29	Correct	18 ms	12144 KB	Output is correct
30	Correct	12 ms	12104 KB	Output is correct
31	Correct	16 ms	12168 KB	Output is correct
32	Correct	20 ms	12144 KB	Output is correct
33	Correct	20 ms	12104 KB	Output is correct
34	Correct	29 ms	12140 KB	Output is correct
35	Correct	19 ms	12140 KB	Output is correct
36	Correct	16 ms	12100 KB	Output is correct
37	Correct	15 ms	12104 KB	Output is correct
38	Correct	15 ms	12160 KB	Output is correct
39	Correct	16 ms	12164 KB	Output is correct

Subtask #4
0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	608 ms	12316 KB	Output is correct
2	Correct	656 ms	12320 KB	Output is correct
3	Correct	630 ms	12336 KB	Output is correct
4	Correct	659 ms	12320 KB	Output is correct
5	Correct	488 ms	12324 KB	Output is correct
6	Correct	505 ms	12352 KB	Output is correct
7	Correct	675 ms	12428 KB	Output is correct
8	Correct	898 ms	12348 KB	Output is correct
9	Correct	829 ms	12468 KB	Output is correct
10	Correct	708 ms	12460 KB	Output is correct
11	Correct	768 ms	12436 KB	Output is correct
12	Correct	722 ms	12488 KB	Output is correct
13	Correct	787 ms	12476 KB	Output is correct
14	Correct	882 ms	12340 KB	Output is correct
15	Correct	820 ms	12452 KB	Output is correct
16	Correct	878 ms	12360 KB	Output is correct
17	Correct	733 ms	12460 KB	Output is correct
18	Incorrect	1805 ms	12320 KB	Wrong Answer [2]
19	Halted	0 ms	0 KB	-

Submission #513835

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 10.0 / 10.0

Subtask #3 12.0 / 12.0

Subtask #4 0 / 71.0

Subtask #1
7.0 / 7.0

Subtask #2
10.0 / 10.0

Subtask #3
12.0 / 12.0

Subtask #4
0 / 71.0