結果

問題 No.2301 Namorientation
ユーザー kotatsugamekotatsugame
提出日時 2023-05-12 21:36:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 163 ms / 3,000 ms
コード長 1,137 bytes
コンパイル時間 698 ms
コンパイル使用メモリ 74,952 KB
実行使用メモリ 22,820 KB
最終ジャッジ日時 2024-11-28 17:33:22
合計ジャッジ時間 10,156 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
using namespace std;
int deg[2<<17];
int N,A[2<<17],B[2<<17];
int from[2<<17];
vector<pair<int,int> >G[2<<17];
bool vis[2<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>A[i]>>B[i];
		A[i]--,B[i]--;
		deg[A[i]]++;
		deg[B[i]]++;
		G[A[i]].push_back(make_pair(B[i],i));
		G[B[i]].push_back(make_pair(A[i],i));
		from[i]=-1;
	}
	vector<int>Q;
	for(int i=0;i<N;i++)if(deg[i]==1)
	{
		Q.push_back(i);
		vis[i]=true;
	}
	for(int i=0;i<Q.size();i++)
	{
		int u=Q[i];
		for(pair<int,int>e:G[u])if(!vis[e.first])
		{
			from[e.second]=u;
			if(--deg[e.first]==1)
			{
				Q.push_back(e.first);
				vis[e.first]=true;
			}
		}
	}
	Q.clear();
	int u=0;
	while(vis[u])u++;
	Q.push_back(u);
	int st=u;
	for(int i=0;i<Q.size();i++)
	{
		int u=Q[i];
		vis[u]=true;
		for(pair<int,int>e:G[u])if(!vis[e.first])
		{
			from[e.second]=u;
			Q.push_back(e.first);
			break;
		}
	}
	for(int i=0;i<N;i++)
	{
		if(from[i]!=-1)
		{
			if(from[i]==A[i])cout<<"->\n";
			else cout<<"<-\n";
		}
		else
		{
			if(st==A[i])cout<<"<-\n";
			else cout<<"->\n";
		}
	}
}
0