oj.uz

Submission #721568

# Submission time Handle Problem Language Result Execution time Memory
721568 2023-04-11T04:42:00 Z minhcool Simurgh (IOI17_simurgh) C++17
30 / 100
 1008 ms 10452 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;

 
int n, m, a[N];
 
int count(vector<int> v){
  if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0) exit(0);
//	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 * N];
int cnt;
int tim[N * N], low[N * N];
int edg[N * N];// backedge that correspond to low
 
int ind[N][N], dep[N * N];
bool find[N * N], answ[N * N], bri[N * N];
 
int par[N * N];
 
vector<int> ask;
 
void dfs(int u, int p){
  if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0) exit(0);
	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){
  if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0) exit(0);
	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;
		}
	}
    return 0;
}
 
int save[N * N];
 
vector<int> oth;
 
void find_oth_edg(int u){
  if((double)clock() / (double)CLOCKS_PER_SEC >= 1.0) exit(0);
	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){
	//exit(0);
	n = n_, m = u.size();
//	cout << u.size() << " " << v.size() << "\n";
	for(int i = 0; i < m; i++){
	//	assert(u.size() > i);
	//	assert(v.size() > i);
	//	cout << u[i] << " " << v[i] << "\n";
	//	continue;
		Adj[u[i]].insert(v[i]);
		Adj[v[i]].insert(u[i]);
		//cout << u[i] << " " << v[i] << "\n";
	//	continue;
		ind[u[i]][v[i]] = ind[v[i]][u[i]] = i;
	}
	//exit(0);
	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]);
		}
	}
	//exit(0);
	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;
		//	if(n > 7) continue;
			dfs(i, i);
		}
	}
//	exit(0);
	for(auto it : ask){
		if(find[it]) continue;
		//if(n > 7) continue;
		int a = u[it], b = v[it];
		if(par[b] != a) swap(a, b);
	//	cout << a << " " << b << " " << par[a] << " " << par[b] << "\n";
	//	if(par[a] != b && par[b] != a) cout << "OK\n";
		if(par[b] != a) exit(0);
	//	cout << par[17] << " " << par[18] << "\n";
		//continue;
		for(int i = 0; i < n; i++) vis[i] = 0;
		Adj[a].erase(b), Adj[b].erase(a);
		roads.clear();
	//	if(n > 7) continue;
		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();
		//if(n > 7) continue;
		// finding other edges apart from the cycle
		for(auto it2 : roads){
			find_oth_edg(u[it2]);
			find_oth_edg(v[it2]);
		}
      //for(int i = 0; i < n; i++) if(!vis[i]) cout << "OK\n";
		for(auto it2 : roads){
		//	cout << "WTF\n";
			vector<int> askk;
			for(auto it : oth) askk.pb(it);
			for(auto it3 : roads) if(it2 != it3) askk.pb(it3);
			//for(auto it : askk) cout << it << " ";
		//	cout << "\n";
			//continue;
			save[it2] = count(askk);
		}
		int mn = 1e9, mx = -1e9;
		for(auto it2 : roads){
			mn = min(mn, save[it2]);
			mx = max(mx, save[it2]);
		}
        //if(n > 7) continue;
		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]];
	}
  //	if(n > 7) exit(0);
	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++) cout << answ[i];
	//cout << "\n";
	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: 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);
      |     ~~~~~~~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 14 ms 632 KB correct
15 Correct 12 ms 604 KB correct
16 Correct 13 ms 596 KB correct
17 Correct 10 ms 596 KB correct
18 Correct 4 ms 468 KB correct
19 Correct 11 ms 616 KB correct
20 Correct 10 ms 596 KB correct
21 Correct 9 ms 596 KB correct
22 Correct 7 ms 468 KB correct
23 Correct 6 ms 468 KB correct
24 Correct 5 ms 476 KB correct
25 Correct 2 ms 468 KB correct
26 Correct 6 ms 468 KB correct
27 Correct 5 ms 468 KB correct
28 Correct 3 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 5 ms 468 KB correct
31 Correct 6 ms 472 KB correct
32 Correct 5 ms 564 KB correct
33 Correct 6 ms 468 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 14 ms 632 KB correct
15 Correct 12 ms 604 KB correct
16 Correct 13 ms 596 KB correct
17 Correct 10 ms 596 KB correct
18 Correct 4 ms 468 KB correct
19 Correct 11 ms 616 KB correct
20 Correct 10 ms 596 KB correct
21 Correct 9 ms 596 KB correct
22 Correct 7 ms 468 KB correct
23 Correct 6 ms 468 KB correct
24 Correct 5 ms 476 KB correct
25 Correct 2 ms 468 KB correct
26 Correct 6 ms 468 KB correct
27 Correct 5 ms 468 KB correct
28 Correct 3 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 5 ms 468 KB correct
31 Correct 6 ms 472 KB correct
32 Correct 5 ms 564 KB correct
33 Correct 6 ms 468 KB correct
34 Incorrect 837 ms 4404 KB WA in grader: NO
35 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 340 KB correct
3 Incorrect 1008 ms 10452 KB Security Violation! Don't try to hack
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 14 ms 632 KB correct
15 Correct 12 ms 604 KB correct
16 Correct 13 ms 596 KB correct
17 Correct 10 ms 596 KB correct
18 Correct 4 ms 468 KB correct
19 Correct 11 ms 616 KB correct
20 Correct 10 ms 596 KB correct
21 Correct 9 ms 596 KB correct
22 Correct 7 ms 468 KB correct
23 Correct 6 ms 468 KB correct
24 Correct 5 ms 476 KB correct
25 Correct 2 ms 468 KB correct
26 Correct 6 ms 468 KB correct
27 Correct 5 ms 468 KB correct
28 Correct 3 ms 468 KB correct
29 Correct 2 ms 468 KB correct
30 Correct 5 ms 468 KB correct
31 Correct 6 ms 472 KB correct
32 Correct 5 ms 564 KB correct
33 Correct 6 ms 468 KB correct
34 Incorrect 837 ms 4404 KB WA in grader: NO
35 Halted 0 ms 0 KB -