제출 #563696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563696		hohohaha	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	217 ms	46312 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
//#define int long long

#define ld long double

const int maxn = 2e5 + 5; 

int n, m;
vector<pair<int, ii> > g[maxn]; ii E[maxn]; 
int tin[maxn]; 
int tinpt; 
int low[maxn]; 
bool bridge[maxn];

stack<int> st; 
int cc[maxn]; 

int q; 
int x[maxn]; 
int y[maxn]; 

vector<pair<int, ii> > g2[maxn]; 
int tout[maxn]; 
int dep[maxn]; 
int par[maxn][20]; 
int parid[maxn]; 
int pardir[maxn]; 
int dir[maxn][20];

int ans[maxn]; 

void dfs_prep(int u, int pid) { 
	tin[u] = low[u] = ++tinpt; 
	st.push(u); 
	
	for(auto e: g[u]) { 
		int v = e.fi, id = e.se.fi, dir = e.se.se; 
		if(id == pid) continue; 
		if(!tin[v]) { 
			dfs_prep(v, id);
			low[u] = min(low[u], low[v]);  
		}
		else if(tin[v] < tin[u]) { 
			low[u] = min(low[u], tin[v]); 
		}
	}
	if(low[u] >= tin[u]) { 
		while(1) { 
			int top = st.top(); 
			cc[top] = u; 
			st.pop(); 
			if(top == u) break; 
		}
		if(pid >= 0) bridge[pid] = 1; 
	}
}

void dfs_prep_2(int u, int p) { 
    tin[u] = ++tinpt; 
    
    fori(bit, 1, 19) { 
        par[u][bit] = par[par[u][bit - 1]][bit - 1]; 
    }
    for(auto e: g2[u]) { 
        int v = e.fi, id = e.se.fi, dir = e.se.se; 
        if(v - p) { 
            dep[v] = dep[u] + 1; 
            par[v][0] = u; 
            parid[v] = id; 
            pardir[v] = dir ^ 1; 
            dfs_prep_2(v, u);
        }
    }
    tout[u] = tinpt; 
}

bool isan(int u, int v) { 
    return tin[u] <= tin[v] and tout[v] <= tout[u]; 
}

void jump(int u, int v, int dir) { 
    if(isan(u, v)) return; 
    
    //cout << "jump " << u << v << endl; 
    
    ford(bit, 19, 0) { 
        if(isan(par[u][bit], v)) continue; 
        ::dir[u][bit] = dir;
        u = par[u][bit];
    }
    ::dir[u][0] = dir; 
    // cout << "lca: " << par[u][0] << endl; 
}

signed main() { 
//	freopen("oneway.inp", "r", stdin); 
//	freopen("oneway.out", "w", stdout); 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	
	cin >> n >> m; 
	fori(i, 1, m) {
		int u, v;
		cin >> u >> v;  
		E[i] = ii(u, v); 
		g[u].eb(make_pair(v, ii(i, 0)));
		g[v].eb(make_pair(u, ii(i, 1))); 
	}
	
	fori(i, 1, n) if(!tin[i]) dfs_prep(i, -1); 
	
	//fori(i, 1, n) cout << cc[i] << endl; 
	
	fori(i, 1, m) if(bridge[i]) g2[cc[E[i].fi]].eb(make_pair(cc[E[i].se], ii(i, 0))), g2[cc[E[i].se]].eb(make_pair(cc[E[i].fi], ii(i, 1)));
//	
	tinpt = 0; 
	fill(tin + 1, tin + n + 1, 0ll); 
    fori(i, 1, n) if(!tin[i]) { 
        par[i][0] = i; 
        dfs_prep_2(i, i);
    }
    
    cin >> q; 
	fori(i, 1, q) { 
		cin >> x[i] >> y[i];
		if(cc[x[i]] == cc[y[i]]) continue;
		jump(cc[x[i]], cc[y[i]], 1); 
		jump(cc[y[i]], cc[x[i]], 2); 
	}
	ford(bit, 19, 1) { 
	   fori(i, 1, n) { 
	       if(dir[i][bit]) { 
	           dir[i][bit - 1] = dir[i][bit]; 
	           dir[par[i][bit - 1]][bit - 1] = dir[i][bit]; 
	       }
	   }
	}
	fori(i, 1, n) { 
	   if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1; 
	}
	fori(i, 1, m) { 
	       if(ans[i] == 1) cout << "R";
	       else if(ans[i] == 2) cout << "L";
	       else cout << "B";
	}
}

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

oneway.cpp: In function 'void dfs_prep(int, int)':
oneway.cpp:49:31: warning: unused variable 'dir' [-Wunused-variable]
   49 |   int v = e.fi, id = e.se.fi, dir = e.se.se;
      |                               ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:77: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  152 |     if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1;
      |                                                                   ~~~~~~~~~~^~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40