oj.uz

Submission #721509

# Submission time Handle Problem Language Result Execution time Memory
721509 2023-04-11T03:32:32 Z minhcool Simurgh (IOI17_simurgh) C++17
0 / 100
 3000 ms 10876 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

#define save savee
#define find findd
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 505 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, a[N];

int count(vector<int> v){
	//for(auto it : v) cout << it << " ";
	//cout << "\n";
	//assert(v.size() == (n - 1));
	if(v.size() != (n - 1)) exit(0);
	return count_common_roads(v);
}

set<int> Adj[N];

bool vis[N];
int cnt;
int tim[N], low[N];
int edg[N];// backedge that correspond to low

int ind[N][N], dep[N];
bool find[N * N], answ[N * N], bri[N * N];

int par[N];

vector<int> ask;

void dfs(int u, int p){
	vis[u] = 1;
	cnt++;
	tim[u] = low[u] = cnt;
	edg[u] = -1;
	for(auto v : Adj[u]){
		if(!vis[v]){
			ask.pb(ind[u][v]);
			dep[v] = dep[u] + 1;
			par[v] = u;
			dfs(v, u);
			if(low[u] > low[v]){
				low[u] = low[v];
				edg[u] = edg[v];
			}
			if(low[v] > tim[u]){
				find[ind[u][v]] = answ[ind[u][v]] = bri[ind[u][v]] = 1;
			}
		}
		else if(v != p){
			if(low[u] > tim[v]){
				low[u] = tim[v];
				edg[u] = ind[u][v];
			}
		}
	}
}

vector<int> roads;

bool get(int u, int need){
	vis[u] = 1;
	if(u == need) return 1;
	for(auto v : Adj[u]){
		if(vis[v]) continue;
		if(get(v, need)){
			roads.pb(ind[u][v]);
			return 1;
		}
	}
}

int save[N];

vector<int> oth;

void find_oth_edg(int u){
	vis[u] = 1;
	for(auto v : Adj[u]){
		if(vis[v]) continue;
		oth.pb(ind[u][v]);
		find_oth_edg(v);
	}
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v){
	n = n_, m = u.size();
	for(int i = 0; i < m; i++){
		Adj[u[i]].insert(v[i]);
		Adj[v[i]].insert(u[i]);
		ind[u[i]][v[i]] = ind[v[i]][u[i]] = i;
	}
	dfs(0, 0);
	for(int i = 0; i < m; i++){
		if(bri[i]){
		//	cout << i << "\n";
			Adj[u[i]].erase(v[i]);
			Adj[v[i]].erase(u[i]);
		}
	}
	for(int i = 0; i < n; i++) vis[i] = 0;
	cnt = 0;
	ask.clear();
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			dep[i] = 0;
			dfs(i, i);
		}
	}
	for(auto it : ask){
		if(find[it]) continue;
		int a = u[it], b = v[it];
		if(par[b] != a) swap(a, b);
		for(int i = 0; i < n; i++) vis[i] = 0;
		Adj[a].erase(b), Adj[b].erase(a);
		roads.clear();
		get(b, a);
		roads.pb(it);
	//	cout << "OK " << it << "\n";
	//	for(auto it2 : roads) cout << it2 << " ";
	//	cout << "\n";
		for(int i = 0; i < n; i++) vis[i] = 0;
		for(int i = 0; i < m; i++){
			if(bri[i]){
				Adj[u[i]].insert(v[i]);
				Adj[v[i]].insert(u[i]);
			}
		}
		for(auto it2 : roads){
			vis[u[it2]] = vis[v[it2]] = 1;
		}
		oth.clear();
		// finding other edges apart from the cycle
		for(auto it2 : roads){
			find_oth_edg(u[it2]);
			find_oth_edg(v[it2]);
		}
		for(auto it2 : roads){
			vector<int> askk = oth;
			for(auto it3 : roads) if(it2 != it3) askk.pb(it3);
			save[it2] = count(askk);
		}
		int mn = oo, mx = -oo;
		for(auto it2 : roads){
			mn = min(mn, save[it2]);
			mx = max(mx, save[it2]);
		}
		if(mn == mx){// then everything equals to zero
			for(auto it2 : roads){
				find[it2] = 1;
				answ[it2] = 0;
			}
		}
		else{
			for(auto it2 : roads){
				find[it2] = 1;
				if(save[it2] == mn) answ[it2] = 1;
				else answ[it2] = 0;
			}
		}
		for(int i = 0; i < m; i++){
			if(bri[i]){
				Adj[u[i]].erase(v[i]);
				Adj[v[i]].erase(u[i]);
			}
		}
	//	assert(par[b] == a);
	//	int c = u[edg[b]], d = v[edg[b]];
	}
	for(int i = 0; i < m; i++){
		if(bri[i]){
			Adj[u[i]].insert(v[i]);
			Adj[v[i]].insert(u[i]);
		}
	}
	vector<int> vv = ask;
	for(int i = 0; i < m; i++) if(bri[i]) vv.pb(i);
	int ori_ans = count(vv);
//	for(int i = 0; i < m; i++) cout << find[i] << " " << answ[i] << "\n";
	for(int i = 0; i < m; i++){
		if(find[i]) continue;
		find[i] = 1;
		int a = u[i], b = v[i];
		if(dep[a] > dep[b]) swap(a, b);
		int temp = ind[b][par[b]];
		vector<int> vv;
		for(int j = 0; j < m; j++) if(bri[j]) vv.pb(j);
		for(auto it : ask) if(it != temp) vv.pb(it);
		vv.pb(i);
		answ[i] = answ[temp] + (count(vv) - ori_ans);
	}
	vector<int> ans;
	for(int i = 0; i < m; i++) if(answ[i]) ans.pb(i);
	//assert(ans.size() == (n - 1));
	return ans;
}

/*

void process(){
	cin >> n;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
*/

Compilation message

simurgh.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
simurgh.cpp: In function 'int count(std::vector<int>)':
simurgh.cpp:26:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |  if(v.size() != (n - 1)) exit(0);
      |     ~~~~~~~~~^~~~~~~~~~
simurgh.cpp: In function 'bool get(int, int)':
simurgh.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 328 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 328 KB correct
6 Correct 1 ms 328 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Execution timed out 3064 ms 340 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 328 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 328 KB correct
6 Correct 1 ms 328 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Execution timed out 3064 ms 340 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 328 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 328 KB correct
6 Correct 1 ms 328 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Execution timed out 3064 ms 340 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 336 KB correct
3 Incorrect 1639 ms 10876 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 328 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 328 KB correct
6 Correct 1 ms 328 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Execution timed out 3064 ms 340 KB Time limit exceeded
11 Halted 0 ms 0 KB -