oj.uz

답안 #721527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721527 2023-04-11T03:46:55 Z minhcool Simurgh (IOI17_simurgh) C++17
13 / 100
 4 ms 468 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){
  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];
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){
  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];
 
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){
	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]);
		}
      if(n > 7) continue;
		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]];
	}
  	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++) 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:27:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |  if(v.size() != (n - 1)) exit(0);
      |     ~~~~~~~~~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:156:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  156 |       if(n > 7) continue;
      |       ^~
simurgh.cpp:157:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  157 |   for(auto it2 : roads){
      |   ^~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 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 0 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 340 KB correct
11 Correct 1 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 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 0 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 340 KB correct
11 Correct 1 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Incorrect 4 ms 468 KB Security Violation! Don't try to hack
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 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 0 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 340 KB correct
11 Correct 1 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Incorrect 4 ms 468 KB Security Violation! Don't try to hack
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB correct
2 Incorrect 0 ms 340 KB Security Violation! Don't try to hack
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 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 0 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 0 ms 340 KB correct
11 Correct 1 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Incorrect 4 ms 468 KB Security Violation! Don't try to hack
15 Halted 0 ms 0 KB -