oj.uz

Submission #831744

# Submission time Handle Problem Language Result Execution time Memory
831744 2023-08-20T13:09:04 Z Rafi22 Simurgh (IOI17_simurgh) C++14
30 / 100
 78 ms 3720 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;

const int N=507,M=507*507;

vector<pair<int,int>>G[N];
int odw[N],c;
int o[N],id[N];
vector<int>st;

int val[M];

void dfs(int v)
{
	odw[v]=++c;
	for(auto [u,i]:G[v])
	{
		if(!odw[u])
		{
			o[u]=v;
			id[u]=i;
			st.pb(i);
			dfs(u);
		}
	}
}

/*int Find(int v)
{
	if(r[v]==v) return v;
	return r[v]=Find(r[v]);
}
int Union(int u,int v)
{
	u=Find(u),v=Find(v);
	r[u]=v;
}

int r[N];

vector<int>get(vector<int>W)
{
	
}*/

int get(int x)
{
	vector<int>Q;
	for(auto y:st) if(y!=x) Q.pb(y);
	return count_common_roads(Q);
}

void dfs1(int v)
{
	odw[v]=++c;
	for(auto [u,i]:G[v])
	{
		if(!odw[u]) dfs1(u);
		else if(odw[u]<odw[v]&&u!=o[v])
		{
			vector<int>V={i};
			st.pb(i);
			int p=-1,x=v;
			while(x!=u)
			{
				if(val[id[x]]) p=id[x];
				else V.pb(id[x]); 
				x=o[x];
			}
			if(p==-1)
			{
				vector<pair<int,int>>W;
				int mx=-inf;
				for(auto x:V) 
				{
					int k=get(x);
					mx=max(mx,k);
					W.pb({k,x});
				}
				for(auto [k,x]:W)
				{
					if(k<mx) val[x]=2;
					else val[x]=1;
				}
			}
			else 
			{
				for(auto x:V) 
				{
					int c1=get(p),c2=get(x);
					if(c1==c2) val[x]=val[p];
					else if(c1<c2) val[x]=1;
					else val[x]=2;
				}
			}
			st.pop_back();
		}
	}
	if(!val[id[v]]) val[id[v]]=2;
}

vector<int>find_roads(int n,vector<int>U,vector<int>V)
{
	int m=sz(U);
	for(int i=0;i<m;i++) 
	{
		G[U[i]].pb({V[i],i});
		G[V[i]].pb({U[i],i});
	}
	dfs(0);
	memset(odw,0,sizeof odw);
	dfs1(0);
	vector<int>ans;
	for(int i=0;i<m;i++) if(val[i]==2) ans.pb(i);
	return ans;
}
/*
int main()
{
	vector<int>X=find_roads(4,{0, 0, 0, 1, 1, 2},{1, 2, 3, 2, 3, 3});
	return 0;
}*/

Compilation message

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:28:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |  for(auto [u,i]:G[v])
      |           ^
simurgh.cpp: In function 'void dfs1(int)':
simurgh.cpp:68:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |  for(auto [u,i]:G[v])
      |           ^
simurgh.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for(auto [k,x]:W)
      |              ^

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 340 KB correct
20 Correct 2 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 0 ms 212 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 340 KB correct
34 Incorrect 78 ms 1504 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 212 KB correct
2 Correct 0 ms 212 KB correct
3 Incorrect 60 ms 3720 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 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 340 KB correct
17 Correct 2 ms 340 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 340 KB correct
20 Correct 2 ms 340 KB correct
21 Correct 2 ms 340 KB correct
22 Correct 1 ms 340 KB correct
23 Correct 1 ms 340 KB correct
24 Correct 1 ms 340 KB correct
25 Correct 0 ms 212 KB correct
26 Correct 1 ms 340 KB correct
27 Correct 1 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 0 ms 340 KB correct
30 Correct 1 ms 340 KB correct
31 Correct 1 ms 340 KB correct
32 Correct 1 ms 340 KB correct
33 Correct 1 ms 340 KB correct
34 Incorrect 78 ms 1504 KB WA in grader: NO
35 Halted 0 ms 0 KB -