oj.uz

Submission #513810

# Submission time Handle Problem Language Result Execution time Memory
513810 2022-01-17T16:19:10 Z fatemetmhr Meetings (JOI19_meetings) C++17
0 / 100
 2000 ms 12384 KB 
//  ~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];

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){
	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;
	for(auto u : adj[c]) if(!rem[u]){
		int t = Query(c, u, v);
		if(t == v){
			remo(u, c);
			remo(c, u);
			adj[u].pb(v);
			adj[c].pb(v);
			adj[v].pb(u);
			adj[v].pb(c);
			return;
		}
		if(t == u){
			sub = u;
			break;
		}
	}
	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++){
		fill(rem, rem + n + 5, false);
		add(0, i);
	}
	for(int i = 0; i < n; i++) for(auto u : adj[i])
		if(i < u) Bridge(i, u);
	return;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12076 KB Output is correct
2 Correct 8 ms 11976 KB Output is correct
3 Correct 6 ms 12032 KB Output is correct
4 Correct 8 ms 11976 KB Output is correct
5 Correct 6 ms 11976 KB Output is correct
6 Incorrect 6 ms 12104 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12076 KB Output is correct
2 Correct 8 ms 11976 KB Output is correct
3 Correct 6 ms 12032 KB Output is correct
4 Correct 8 ms 11976 KB Output is correct
5 Correct 6 ms 11976 KB Output is correct
6 Incorrect 6 ms 12104 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12076 KB Output is correct
2 Correct 8 ms 11976 KB Output is correct
3 Correct 6 ms 12032 KB Output is correct
4 Correct 8 ms 11976 KB Output is correct
5 Correct 6 ms 11976 KB Output is correct
6 Incorrect 6 ms 12104 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

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