oj.uz

Submission #582894

# Submission time Handle Problem Language Result Execution time Memory
582894 2022-06-24T14:33:34 Z Koosha_mv Simurgh (IOI17_simurgh) C++14
51 / 100
 253 ms 11144 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
 
const int N=505*505;
 
int n,m,askt,h[N],ok[N],vis[N],last[N],f[N],A[N],B[N];
pair<int,int> par[N];
vector<int> tree;
vector<pair<int,int>> g[N];

int getpar(int u){
	if(f[u]<0) return u;
	return f[u]=getpar(f[u]);
}
void merge(int u,int v){
	u=getpar(u),v=getpar(v);
	if(f[u]>f[v]) swap(u,v);
	f[u]+=f[v];
	f[v]=u;
}
int ask(vector<int> vec){
	return count_common_roads(vec);
}
int get(vector<int> vec){
	fill(f,f+n,-1);
	int sum=0;
	for(auto id : vec){
		merge(A[id],B[id]);
	}
	for(auto id : tree){
		int u=getpar(A[id]),v=getpar(B[id]);
		if(u==v) continue ;
		merge(u,v);
		vec.pb(id);
		sum+=ok[id];
	}
	return ask(vec)-sum;
}
void dfs(int u){
	vis[u]=1;
	for(auto [v,id] : g[u]){
		if(vis[v]) continue ;
		tree.pb(id);
		h[v]=h[u]+1;
		par[v]={u,id};
		dfs(v);
	}
}
vector<int> G(vector<int> vec,int ad,int dl){
	vec.pb(ad);
	f(i,0,vec.size()){
		if(vec[i]==dl){
			vec.erase(vec.begin()+i);
		}
	}
	return vec;
}
vector<int> find_roads(int _n,vector<int> _B,vector<int> _A){
	fill(ok,ok+N,-1);
	// build graph
	vector<int> ans;
	n=_n,m=_A.size();
	f(i,0,m) A[i]=_A[i],B[i]=_B[i],g[A[i]].pb({B[i],i}),g[B[i]].pb({A[i],i});
	
	//find a tree
	dfs(0);
	askt=ask(tree);
	f(i,0,m){
		int u=A[i],v=B[i],mx=askt,cnt=0,edge=0;
		if(abs(h[u]-h[v])==1) continue ;
		if(h[u]>h[v]) swap(u,v);
		for(int x=v;x!=u;x=par[x].F){
			if(ok[par[x].S]!=-1){
				cnt++;
				edge=par[x].S;
			}
		}
		if(cnt==h[v]-h[u]) continue ;
		//cout<<u<<" -> "<<v<<endl;
		if(cnt>0){
			vector<int> prt=G(tree,i,edge);
			maxm(mx,ask(prt)+ok[edge]);
		}
		for(int x=v;x!=u;x=par[x].F){
			if(ok[par[x].S]!=-1) continue ;
			vector<int> prt=G(tree,i,par[x].S);
			last[par[x].S]=ask(prt);
			maxm(mx,last[par[x].S]);
		}
		for(int x=v;x!=u;x=par[x].F){
			if(ok[par[x].S]!=-1) continue ;
			if(last[par[x].S]==mx) ok[par[x].S]=0;
			else ok[par[x].S]=1;
		}
	}
	for(auto id : tree) if(ok[id]==-1) ok[id]=1;
	//dbga(ok,0,m);
	
	//main
	f(i,0,m){
		vector<int> vec;
		vec.pb(i);
		if(get(vec)==1){
			ans.pb(i);
		}
	}
	//dbgv(ans);
	return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:61:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |  for(auto [v,id] : g[u]){
      |           ^
simurgh.cpp: In function 'std::vector<int> G(std::vector<int>, int, int)':
simurgh.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   71 |  f(i,0,vec.size()){
      |    ~~~~~~~~~~~~~~              
simurgh.cpp:71:2: note: in expansion of macro 'f'
   71 |  f(i,0,vec.size()){
      |  ^

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB correct
2 Correct 4 ms 7252 KB correct
3 Correct 5 ms 7252 KB correct
4 Correct 4 ms 7252 KB correct
5 Correct 5 ms 7252 KB correct
6 Correct 6 ms 7252 KB correct
7 Correct 4 ms 7252 KB correct
8 Correct 4 ms 7252 KB correct
9 Correct 4 ms 7252 KB correct
10 Correct 4 ms 7252 KB correct
11 Correct 4 ms 7252 KB correct
12 Correct 5 ms 7252 KB correct
13 Correct 4 ms 7320 KB correct
14 Correct 7 ms 7324 KB correct
15 Correct 7 ms 7380 KB correct
16 Correct 7 ms 7392 KB correct
17 Correct 8 ms 7380 KB correct
18 Correct 5 ms 7252 KB correct
19 Correct 7 ms 7324 KB correct
20 Correct 7 ms 7380 KB correct
21 Correct 7 ms 7324 KB correct
22 Correct 7 ms 7372 KB correct
23 Correct 6 ms 7380 KB correct
24 Correct 6 ms 7252 KB correct
25 Correct 4 ms 7320 KB correct
26 Correct 6 ms 7380 KB correct
27 Correct 5 ms 7324 KB correct
28 Correct 5 ms 7252 KB correct
29 Correct 4 ms 7252 KB correct
30 Correct 5 ms 7380 KB correct
31 Correct 6 ms 7380 KB correct
32 Correct 6 ms 7252 KB correct
33 Correct 7 ms 7324 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB correct
2 Correct 4 ms 7252 KB correct
3 Correct 5 ms 7252 KB correct
4 Correct 4 ms 7252 KB correct
5 Correct 5 ms 7252 KB correct
6 Correct 6 ms 7252 KB correct
7 Correct 4 ms 7252 KB correct
8 Correct 4 ms 7252 KB correct
9 Correct 4 ms 7252 KB correct
10 Correct 4 ms 7252 KB correct
11 Correct 4 ms 7252 KB correct
12 Correct 5 ms 7252 KB correct
13 Correct 4 ms 7320 KB correct
14 Correct 7 ms 7324 KB correct
15 Correct 7 ms 7380 KB correct
16 Correct 7 ms 7392 KB correct
17 Correct 8 ms 7380 KB correct
18 Correct 5 ms 7252 KB correct
19 Correct 7 ms 7324 KB correct
20 Correct 7 ms 7380 KB correct
21 Correct 7 ms 7324 KB correct
22 Correct 7 ms 7372 KB correct
23 Correct 6 ms 7380 KB correct
24 Correct 6 ms 7252 KB correct
25 Correct 4 ms 7320 KB correct
26 Correct 6 ms 7380 KB correct
27 Correct 5 ms 7324 KB correct
28 Correct 5 ms 7252 KB correct
29 Correct 4 ms 7252 KB correct
30 Correct 5 ms 7380 KB correct
31 Correct 6 ms 7380 KB correct
32 Correct 6 ms 7252 KB correct
33 Correct 7 ms 7324 KB correct
34 Correct 253 ms 8828 KB correct
35 Correct 242 ms 8816 KB correct
36 Correct 176 ms 8544 KB correct
37 Correct 18 ms 7432 KB correct
38 Correct 249 ms 8836 KB correct
39 Correct 217 ms 8708 KB correct
40 Correct 169 ms 8552 KB correct
41 Correct 253 ms 8840 KB correct
42 Correct 240 ms 8828 KB correct
43 Correct 137 ms 8308 KB correct
44 Correct 117 ms 8016 KB correct
45 Correct 124 ms 8108 KB correct
46 Correct 100 ms 7952 KB correct
47 Correct 45 ms 7636 KB correct
48 Correct 9 ms 7380 KB correct
49 Correct 17 ms 7380 KB correct
50 Correct 46 ms 7564 KB correct
51 Correct 122 ms 8096 KB correct
52 Correct 107 ms 8024 KB correct
53 Correct 102 ms 7892 KB correct
54 Correct 139 ms 8316 KB correct
55 Correct 120 ms 8108 KB correct
56 Correct 119 ms 8100 KB correct
57 Correct 128 ms 8112 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB correct
2 Correct 5 ms 7252 KB correct
3 Incorrect 211 ms 11144 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB correct
2 Correct 4 ms 7252 KB correct
3 Correct 5 ms 7252 KB correct
4 Correct 4 ms 7252 KB correct
5 Correct 5 ms 7252 KB correct
6 Correct 6 ms 7252 KB correct
7 Correct 4 ms 7252 KB correct
8 Correct 4 ms 7252 KB correct
9 Correct 4 ms 7252 KB correct
10 Correct 4 ms 7252 KB correct
11 Correct 4 ms 7252 KB correct
12 Correct 5 ms 7252 KB correct
13 Correct 4 ms 7320 KB correct
14 Correct 7 ms 7324 KB correct
15 Correct 7 ms 7380 KB correct
16 Correct 7 ms 7392 KB correct
17 Correct 8 ms 7380 KB correct
18 Correct 5 ms 7252 KB correct
19 Correct 7 ms 7324 KB correct
20 Correct 7 ms 7380 KB correct
21 Correct 7 ms 7324 KB correct
22 Correct 7 ms 7372 KB correct
23 Correct 6 ms 7380 KB correct
24 Correct 6 ms 7252 KB correct
25 Correct 4 ms 7320 KB correct
26 Correct 6 ms 7380 KB correct
27 Correct 5 ms 7324 KB correct
28 Correct 5 ms 7252 KB correct
29 Correct 4 ms 7252 KB correct
30 Correct 5 ms 7380 KB correct
31 Correct 6 ms 7380 KB correct
32 Correct 6 ms 7252 KB correct
33 Correct 7 ms 7324 KB correct
34 Correct 253 ms 8828 KB correct
35 Correct 242 ms 8816 KB correct
36 Correct 176 ms 8544 KB correct
37 Correct 18 ms 7432 KB correct
38 Correct 249 ms 8836 KB correct
39 Correct 217 ms 8708 KB correct
40 Correct 169 ms 8552 KB correct
41 Correct 253 ms 8840 KB correct
42 Correct 240 ms 8828 KB correct
43 Correct 137 ms 8308 KB correct
44 Correct 117 ms 8016 KB correct
45 Correct 124 ms 8108 KB correct
46 Correct 100 ms 7952 KB correct
47 Correct 45 ms 7636 KB correct
48 Correct 9 ms 7380 KB correct
49 Correct 17 ms 7380 KB correct
50 Correct 46 ms 7564 KB correct
51 Correct 122 ms 8096 KB correct
52 Correct 107 ms 8024 KB correct
53 Correct 102 ms 7892 KB correct
54 Correct 139 ms 8316 KB correct
55 Correct 120 ms 8108 KB correct
56 Correct 119 ms 8100 KB correct
57 Correct 128 ms 8112 KB correct
58 Correct 4 ms 7252 KB correct
59 Correct 5 ms 7252 KB correct
60 Incorrect 211 ms 11144 KB WA in grader: NO
61 Halted 0 ms 0 KB -