제출 #831744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831744		Rafi22	Simurgh (IOI17_simurgh)	C++14	30 / 100	78 ms	3720 KiB

simurgh

#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;
}*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30