結果
| 問題 | No.2301 Namorientation |
| ユーザー |
 t9unkubj
|
| 提出日時 | 2024-09-30 07:18:15 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,244 bytes |
| コンパイル時間 | 4,923 ms |
| コンパイル使用メモリ | 296,572 KB |
| 実行使用メモリ | 68,060 KB |
| 最終ジャッジ日時 | 2024-09-30 07:18:41 |
| 合計ジャッジ時間 | 20,616 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
ソースコード
#ifdef t9unkubj
#include"template.h"
//#include"template_no_debug.h"
#else
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
#define dbg(...) 199958
using namespace std;
#include<bits/stdc++.h>
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T>using vvvc=vvc<vc<T>>;
using vi=vc<int>;
using vvi=vc<vi>;
using vvvi=vc<vvi>;
using vl=vc<ll>;
using vvl=vc<vl>;
using vvvl=vc<vvl>;
template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;
template<class T>using bipq=priority_queue<T>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define is insert
#define bg begin()
#define ed end()
void scan(int&a) { cin >> a; }
void scan(ll&a) { cin >> a; }
void scan(string&a) { cin >> a; }
void scan(char&a) { cin >> a; }
void scan(uint&a) { cin >> a; }
void scan(ull&a) { cin >> a; }
void scan(bool&a) { cin >> a; }
void scan(ld&a){ cin>> a;}
template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }
void read() {}
template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }
#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);
#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);
#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);
#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);
#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);
void print(int a) { cout << a; }
void print(ll a) { cout << a; }
void print(string a) { cout << a; }
void print(char a) { cout << a; }
void print(uint a) { cout << a; }
void print(bool a) { cout << a; }
void print(ull a) { cout << a; }
void print(double a) { cout << a; }
void print(ld a){ cout<< a; }
template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}
void PRT() { cout <<endl; return ; }
template<class T> void PRT(T a) { print(a); cout <<endl; return; }
template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
void YesNo(bool b){
cout<<(b?"Yes":"No")<<endl;
}
void Yes(){
cout<<"Yes"<<endl;
}
void No(){
cout<<"No"<<endl;
}
template<class T>
int popcount(T n){
return __builtin_popcountll(n);
}
template<class T>
T sum(vc<T>&a){
return accumulate(all(a),T(0));
}
template<class T>
T max(vc<T>&a){
return *max_element(all(a));
}
template<class T>
T min(vc<T>&a){
return *min_element(all(a));
}
template<class T>
void unique(vc<T>&a){
a.erase(unique(all(a)),a.end());
}
vvi readgraph(int n,int m,int off = -1){
vvi g(n);
rep(i, m){
int u,v;
cin>>u>>v;
u+=off,v+=off;
g[u].push_back(v);
g[v].push_back(u);
}
return g;
}
vvi readtree(int n,int off=-1){
return readgraph(n,n-1,off);
}
template<class T>
vc<T> presum(vc<T> &a){
vc<T> ret(a.size()+1);
rep(i,a.size())ret[i+1]=ret[i]+a[i];
return ret;
}
template<class T, class F>
vc<T> &operator+=(vc<T> &a,F b){
for (auto&v:a)v += b;
return a;
}
template<class T, class F>
vc<T> &operator-=(vc<T>&a,F b){
for (auto&v:a)v-=b;
return a;
}
template<class T, class F>
vc<T> &operator*=(vc<T>&a,F b){
for (auto&v:a)v*=b;
return a;
}
#endif
double pass_time=0;
/*
https://atcoder.jp/contests/arc039/tasks/arc039_d
https://kntychance.hatenablog.jp/entry/2022/09/16/161858
*/
struct Edge{
int from;
int to;
int id;
};
struct graph{
vector<vector<Edge>>g;
vector<int>low,ord;
vector<int>ea,eb;
vector<int>used;
int n;
graph(int n):n(n),g(n),low(n),ord(n){}
int edge_num=0;
void add_edge(int a,int b,int is_both=1){
g[a].push_back({a,b,edge_num});
if(is_both)g[b].push_back({b,a,edge_num});
ea.push_back(a);
eb.push_back(b);
used.push_back(0);
edge_num++;
}
struct cycle_scanner{
vector<int>seen,finish;
vector<Edge>hist;
int n;
vector<vector<Edge>>g;
cycle_scanner(vector<vector<Edge>>g):g(g),n(g.size()){
}
int dfs(int now,const Edge&pre,int can_rev){
seen[now]=1;
hist.push_back(pre);
for(auto&e:g[now]){
if(can_rev==0&&pre.id==e.id)continue;
if(finish[e.to]){
continue;
}
if(seen[e.to]&&!finish[e.to]){
hist.push_back(e);
return e.to;
}
int res=dfs(e.to,e,can_rev);
if(res!=-1)return res;
}
finish[now]=1;
hist.pop_back();
return -1;
}
vector<Edge>constructer(int pos){
vector<Edge>res;
while(hist.size()){
auto p=hist.back();hist.pop_back();
res.push_back(p);
if(p.from==pos)break;
}
reverse(res.begin(), res.end());
return res;
}
//有向グラフなら1,そうでないなら0を与える
vector<Edge>find_v(int can_rev){
seen.resize(n),finish.resize(n);
int pos=-1;
for(int i=0;i<n;i++){
if(seen[i])continue;
pos=dfs(i,{-1,-1,-1},can_rev);
if(pos!=-1){
return constructer(pos);
}
}
return {};
}
};
//有向グラフなら1,そうでないなら0を与える
vector<Edge> cycle_scan(int can_rev){
cycle_scanner cyc(g);
return cyc.find_v(can_rev);
}
int lowlinked=0;
void lowlink(){
if(lowlinked)return;
lowlinked=1;
vector<int>seen(n);
auto dfs=[&](auto&dfs,int u,int v,int&now)->int{
seen[u]=1;
ord[u]=now++;
low[u]=ord[u];
for(auto [from,x,i]:g[u]){
if(i==v)continue;
if(seen[x]){
low[u]=min(low[u],ord[x]);
}else{
used[i]=1;
low[u]=min(low[u],dfs(dfs,x,i,now));
}
}
return low[u];
};
int now=0;
for(int i=0;i<n;i++){
if(!seen[i]){
dfs(dfs,i,-1,now);
}
}
}
vector<int>two_comp_num;
vector<vector<int>>two_comp;
void make_two_comp(){
if(two_comp.size())return;
lowlink();
two_comp_num=vector<int>(n);
vector<vector<int>>res;
dfs1(0,-1,res);
for(int i=0;i<int(res.size());i++){
for(auto x:res[i]){
two_comp_num[x]=i;
}
}
two_comp=res;
}
void dfs2(int u,int v,vector<int>&vs);
int is_bridge(int i){
if(!used[i])return 0;
int a1=ea[i],a2=eb[i];
if(ord[a1]>ord[a2])swap(a1,a2);
if(ord[a1]>=low[a2])return 0;
return 1;
}
void dfs1(int u,int v,vector<vector<int>>&res){
vector<int>vs{u};
for(auto [_,x,i]:g[u]){
if(x==v)continue;
if(!used[i])continue;
if(!is_bridge(i)){
dfs2(x,u,res,vs);
}else{
dfs1(x,u,res);
}
}
res.push_back(vs);
}
void dfs2(int u,int v,vector<vector<int>>&res,vector<int>&vs){
vs.push_back(u);
for(auto [_,x,i]:g[u]){
if(x==v)continue;
if(!used[i])continue;
if(!is_bridge(i)){
dfs2(x,u,res,vs);
}else{
dfs1(x,u,res);
}
}
}
vector<vector<int>>two_g;//二重辺連結成分分解して成分ごとに縮約した気
void make_two_g(){
make_two_comp();
auto res=two_comp;
two_g.resize(res.size());
for(int i=0;i<(int)ea.size();i++){
if(two_comp_num[ea[i]]!=two_comp_num[eb[i]]){
two_g[two_comp_num[ea[i]]].push_back(two_comp_num[eb[i]]);
two_g[two_comp_num[eb[i]]].push_back(two_comp_num[ea[i]]);
}
}
}
//https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_A
vector<int>is_art;
void make_art(){
lowlink();
is_art.resize(n);
int res=0;
for(auto [_,x,i]:g[0]){
if(used[i])res++;
}
is_art[0]=res>=2;
for(int i=1;i<n;i++){
for(auto [_,x,idx]:g[i]){
if(used[idx]&&ord[i]<=low[x])is_art[i]=1;
}
}
}
//なんもわかんねーなにこれ
//https://ei1333.github.io/luzhiled/snippets/graph/bi-connected-components.html
//https://judge.yosupo.jp/submission/226252
vector<vector<pair<int,int>>> bc;//おなじ連結成分に属している辺
vector<vector<int>>bcs;//頂点
void bic(){
lowlink();
vector<int>used(n);
vector<pair<int,int>>tmp;
auto dfs=[&](auto&dfs,int u,int v)->void{
used[u]=1;
for(auto [_,x,idx]:g[u]){
if(x==v)continue;
if(!used[x]||ord[x]<ord[u]){
tmp.push_back(minmax(x,u));
}
if(!used[x]){
dfs(dfs,x,u);
if(low[x]>=ord[u]){
bc.push_back(vector<pair<int,int>>());
while(1){
auto p=tmp.back();tmp.pop_back();
bc.back().push_back(p);
if(p.first==min(x,u)&&p.second==max(x,u)){
break;
}
}
}
}
}
if(g[u].size()==0){//孤立点
bcs.push_back(vector<int>{u});
}
};
for(int i=0;i<n;i++){
if(!used[i])dfs(dfs,i,-1);
}
vector<int>added(n);
for(auto x:bc){
bcs.push_back(vector<int>());
for(auto [a,b]:x){
auto add=[&](int x){
if(added[x])return;
bcs.back().push_back(x);
added[x]=1;
};
add(a),add(b);
}
for(auto x:bcs.back())added[x]=0;
}
}
};
void solve(){
INT(n);
vector<vector<pair<int,int>>>g(n);
graph G(n);
vi a(n),b(n);
rep(i,n){
cin>>a[i]>>b[i];
--a[i],--b[i];
G.add_edge(a[i],b[i],1);
g[a[i]].pb({b[i],i});
g[b[i]].pb({a[i],i});
}
vector<string>ans(n);
auto res=G.cycle_scan(0);
vi is(n);
for(auto [to,from,id]:res){
dbg(to);
is[to]=1;
ans[id]="->";
}
auto dfs=[&](auto&dfs,int now,int pre)->void{
for(auto&[x,i]:g[now]){
if(x==pre)continue;
if(is[x])continue;
if(a[i]==x){
ans[i]="->";
}else ans[i]="<-";
dfs(dfs,x,now);
}
};
rep(i,n){
if(is[i]){
dfs(dfs,i,-1);
}
}
rep(i,n)PRT(ans[i]);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
pass_time=clock();
int t=1;
//cin>>t;
while(t--)solve();
pass_time=clock()-pass_time;
dbg(pass_time/CLOCKS_PER_SEC);
}