oj.uz

Submission #721570

# Submission time Handle Problem Language Result Execution time Memory
721570 2023-04-11T04:42:52 Z minhcool Simurgh (IOI17_simurgh) C++17
30 / 100
 1665 ms 11368 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 = 1005 + 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 0 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 468 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 468 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 468 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 468 KB correct
14 Correct 10 ms 772 KB correct
15 Correct 10 ms 752 KB correct
16 Correct 10 ms 724 KB correct
17 Correct 9 ms 724 KB correct
18 Correct 3 ms 596 KB correct
19 Correct 8 ms 756 KB correct
20 Correct 7 ms 744 KB correct
21 Correct 7 ms 724 KB correct
22 Correct 6 ms 596 KB correct
23 Correct 4 ms 596 KB correct
24 Correct 4 ms 696 KB correct
25 Correct 1 ms 596 KB correct
26 Correct 4 ms 596 KB correct
27 Correct 3 ms 596 KB correct
28 Correct 2 ms 596 KB correct
29 Correct 1 ms 596 KB correct
30 Correct 4 ms 596 KB correct
31 Correct 4 ms 596 KB correct
32 Correct 4 ms 596 KB correct
33 Correct 4 ms 696 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 468 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 468 KB correct
14 Correct 10 ms 772 KB correct
15 Correct 10 ms 752 KB correct
16 Correct 10 ms 724 KB correct
17 Correct 9 ms 724 KB correct
18 Correct 3 ms 596 KB correct
19 Correct 8 ms 756 KB correct
20 Correct 7 ms 744 KB correct
21 Correct 7 ms 724 KB correct
22 Correct 6 ms 596 KB correct
23 Correct 4 ms 596 KB correct
24 Correct 4 ms 696 KB correct
25 Correct 1 ms 596 KB correct
26 Correct 4 ms 596 KB correct
27 Correct 3 ms 596 KB correct
28 Correct 2 ms 596 KB correct
29 Correct 1 ms 596 KB correct
30 Correct 4 ms 596 KB correct
31 Correct 4 ms 596 KB correct
32 Correct 4 ms 596 KB correct
33 Correct 4 ms 696 KB correct
34 Incorrect 733 ms 4708 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 468 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 468 KB correct
14 Correct 10 ms 772 KB correct
15 Correct 10 ms 752 KB correct
16 Correct 10 ms 724 KB correct
17 Correct 9 ms 724 KB correct
18 Correct 3 ms 596 KB correct
19 Correct 8 ms 756 KB correct
20 Correct 7 ms 744 KB correct
21 Correct 7 ms 724 KB correct
22 Correct 6 ms 596 KB correct
23 Correct 4 ms 596 KB correct
24 Correct 4 ms 696 KB correct
25 Correct 1 ms 596 KB correct
26 Correct 4 ms 596 KB correct
27 Correct 3 ms 596 KB correct
28 Correct 2 ms 596 KB correct
29 Correct 1 ms 596 KB correct
30 Correct 4 ms 596 KB correct
31 Correct 4 ms 596 KB correct
32 Correct 4 ms 596 KB correct
33 Correct 4 ms 696 KB correct
34 Incorrect 733 ms 4708 KB WA in grader: NO
35 Halted 0 ms 0 KB -