oj.uz

Submission #582896

# Submission time Handle Problem Language Result Execution time Memory
582896 2022-06-24T14:39:38 Z Koosha_mv Simurgh (IOI17_simurgh) C++14
70 / 100
 380 ms 13736 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> P(int u,int x){
	vector<int> res;
	f(i,0,x+1){
		res.pb(g[u][i].S);
	}
	return res;
}
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(u,0,n){
		vector<int> vec;
		int deg=get(P(u,g[u].size()-1));
		f(i,0,deg){
			int l=-1,r=g[u].size();
			while(l+1<r){
				int mid=(l+r)>>1;
				if(get(P(u,mid))<=i){
					l=mid;
				}
				else{
					r=mid;
				}
			}
			ans.pb(g[u][r].S);
		}
	}
	sort(all(ans));
	ans.resize(unique(all(ans))-ans.begin());
	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 4 ms 7252 KB correct
2 Correct 6 ms 7316 KB correct
3 Correct 4 ms 7332 KB correct
4 Correct 4 ms 7252 KB correct
5 Correct 4 ms 7252 KB correct
6 Correct 4 ms 7252 KB correct
7 Correct 4 ms 7236 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 5 ms 7252 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB correct
2 Correct 6 ms 7316 KB correct
3 Correct 4 ms 7332 KB correct
4 Correct 4 ms 7252 KB correct
5 Correct 4 ms 7252 KB correct
6 Correct 4 ms 7252 KB correct
7 Correct 4 ms 7236 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 5 ms 7252 KB correct
14 Correct 7 ms 7380 KB correct
15 Correct 7 ms 7380 KB correct
16 Correct 6 ms 7400 KB correct
17 Correct 7 ms 7380 KB correct
18 Correct 5 ms 7252 KB correct
19 Correct 7 ms 7380 KB correct
20 Correct 6 ms 7380 KB correct
21 Correct 6 ms 7332 KB correct
22 Correct 6 ms 7380 KB correct
23 Correct 6 ms 7440 KB correct
24 Correct 6 ms 7380 KB correct
25 Correct 5 ms 7252 KB correct
26 Correct 6 ms 7380 KB correct
27 Correct 5 ms 7380 KB correct
28 Correct 5 ms 7252 KB correct
29 Correct 5 ms 7252 KB correct
30 Correct 6 ms 7252 KB correct
31 Correct 6 ms 7252 KB correct
32 Correct 6 ms 7372 KB correct
33 Correct 6 ms 7380 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB correct
2 Correct 6 ms 7316 KB correct
3 Correct 4 ms 7332 KB correct
4 Correct 4 ms 7252 KB correct
5 Correct 4 ms 7252 KB correct
6 Correct 4 ms 7252 KB correct
7 Correct 4 ms 7236 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 5 ms 7252 KB correct
14 Correct 7 ms 7380 KB correct
15 Correct 7 ms 7380 KB correct
16 Correct 6 ms 7400 KB correct
17 Correct 7 ms 7380 KB correct
18 Correct 5 ms 7252 KB correct
19 Correct 7 ms 7380 KB correct
20 Correct 6 ms 7380 KB correct
21 Correct 6 ms 7332 KB correct
22 Correct 6 ms 7380 KB correct
23 Correct 6 ms 7440 KB correct
24 Correct 6 ms 7380 KB correct
25 Correct 5 ms 7252 KB correct
26 Correct 6 ms 7380 KB correct
27 Correct 5 ms 7380 KB correct
28 Correct 5 ms 7252 KB correct
29 Correct 5 ms 7252 KB correct
30 Correct 6 ms 7252 KB correct
31 Correct 6 ms 7252 KB correct
32 Correct 6 ms 7372 KB correct
33 Correct 6 ms 7380 KB correct
34 Correct 67 ms 8624 KB correct
35 Correct 70 ms 8604 KB correct
36 Correct 61 ms 8404 KB correct
37 Correct 22 ms 7436 KB correct
38 Correct 67 ms 8644 KB correct
39 Correct 66 ms 8552 KB correct
40 Correct 58 ms 8412 KB correct
41 Correct 68 ms 8532 KB correct
42 Correct 68 ms 8628 KB correct
43 Correct 48 ms 8208 KB correct
44 Correct 40 ms 7924 KB correct
45 Correct 43 ms 8020 KB correct
46 Correct 39 ms 7892 KB correct
47 Correct 30 ms 7636 KB correct
48 Correct 16 ms 7380 KB correct
49 Correct 23 ms 7452 KB correct
50 Correct 34 ms 7656 KB correct
51 Correct 40 ms 8000 KB correct
52 Correct 41 ms 8012 KB correct
53 Correct 39 ms 7892 KB correct
54 Correct 47 ms 8208 KB correct
55 Correct 44 ms 7892 KB correct
56 Correct 45 ms 8004 KB correct
57 Correct 48 ms 7996 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB correct
2 Correct 4 ms 7252 KB correct
3 Correct 217 ms 11152 KB correct
4 Correct 366 ms 13604 KB correct
5 Correct 366 ms 13668 KB correct
6 Correct 361 ms 13644 KB correct
7 Correct 349 ms 13736 KB correct
8 Correct 336 ms 13604 KB correct
9 Correct 374 ms 13600 KB correct
10 Correct 357 ms 13612 KB correct
11 Correct 356 ms 13592 KB correct
12 Correct 368 ms 13656 KB correct
13 Correct 4 ms 7252 KB correct
14 Correct 356 ms 13520 KB correct
15 Correct 380 ms 13636 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB correct
2 Correct 6 ms 7316 KB correct
3 Correct 4 ms 7332 KB correct
4 Correct 4 ms 7252 KB correct
5 Correct 4 ms 7252 KB correct
6 Correct 4 ms 7252 KB correct
7 Correct 4 ms 7236 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 5 ms 7252 KB correct
14 Correct 7 ms 7380 KB correct
15 Correct 7 ms 7380 KB correct
16 Correct 6 ms 7400 KB correct
17 Correct 7 ms 7380 KB correct
18 Correct 5 ms 7252 KB correct
19 Correct 7 ms 7380 KB correct
20 Correct 6 ms 7380 KB correct
21 Correct 6 ms 7332 KB correct
22 Correct 6 ms 7380 KB correct
23 Correct 6 ms 7440 KB correct
24 Correct 6 ms 7380 KB correct
25 Correct 5 ms 7252 KB correct
26 Correct 6 ms 7380 KB correct
27 Correct 5 ms 7380 KB correct
28 Correct 5 ms 7252 KB correct
29 Correct 5 ms 7252 KB correct
30 Correct 6 ms 7252 KB correct
31 Correct 6 ms 7252 KB correct
32 Correct 6 ms 7372 KB correct
33 Correct 6 ms 7380 KB correct
34 Correct 67 ms 8624 KB correct
35 Correct 70 ms 8604 KB correct
36 Correct 61 ms 8404 KB correct
37 Correct 22 ms 7436 KB correct
38 Correct 67 ms 8644 KB correct
39 Correct 66 ms 8552 KB correct
40 Correct 58 ms 8412 KB correct
41 Correct 68 ms 8532 KB correct
42 Correct 68 ms 8628 KB correct
43 Correct 48 ms 8208 KB correct
44 Correct 40 ms 7924 KB correct
45 Correct 43 ms 8020 KB correct
46 Correct 39 ms 7892 KB correct
47 Correct 30 ms 7636 KB correct
48 Correct 16 ms 7380 KB correct
49 Correct 23 ms 7452 KB correct
50 Correct 34 ms 7656 KB correct
51 Correct 40 ms 8000 KB correct
52 Correct 41 ms 8012 KB correct
53 Correct 39 ms 7892 KB correct
54 Correct 47 ms 8208 KB correct
55 Correct 44 ms 7892 KB correct
56 Correct 45 ms 8004 KB correct
57 Correct 48 ms 7996 KB correct
58 Correct 5 ms 7252 KB correct
59 Correct 4 ms 7252 KB correct
60 Correct 217 ms 11152 KB correct
61 Correct 366 ms 13604 KB correct
62 Correct 366 ms 13668 KB correct
63 Correct 361 ms 13644 KB correct
64 Correct 349 ms 13736 KB correct
65 Correct 336 ms 13604 KB correct
66 Correct 374 ms 13600 KB correct
67 Correct 357 ms 13612 KB correct
68 Correct 356 ms 13592 KB correct
69 Correct 368 ms 13656 KB correct
70 Correct 4 ms 7252 KB correct
71 Correct 356 ms 13520 KB correct
72 Correct 380 ms 13636 KB correct
73 Correct 5 ms 7252 KB correct
74 Incorrect 315 ms 13632 KB WA in grader: NO
75 Halted 0 ms 0 KB -