| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 141408 | 12tqian | One-Way Streets (CEOI17_oneway) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const double PI = 4 * atan(1);
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
void fast_io(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
void io(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
fast_io();
}
const int MAX = 1e5 + 5;
const int SZ = 1e5 + 5;
vi adj1[MAX];
vi adj[MAX];
vpi paths;
int ans[MAX];
map<pii, int> um;
map<int, int> convert;
map<pii, pii> check;
map<pii, int> ind;
map<pii, int> res;
vpi all;
vi t[MAX];
int N;
template<int SZ> struct DSU{
int par[SZ], sz[SZ];
DSU(){
for(int i = 0; i<SZ; i++){
par[i] = i;
sz[i] = 1;
}
}
int get(int x){
if(par[x] != x){
par[x] = get(par[x]);
}
return par[x];
}
bool unite(int x, int y){
x = get(x);
y = get(y);
if(x == y){
return false;
}
if(sz[x] < sz[y]){
swap(x, y);
}
sz[x] += sz[y];
par[y] = x;
return true;
}
};
DSU<MAX> d;
vector<vector<pair<int, int>>> fin;
void addEdge(int u, int v) {
if(u == v) return;
adj1[u].push_back(v), adj1[v].push_back(u);
}
int ti = 0, disc[SZ], low[SZ], comp[SZ], parent[SZ];
vector<pair<int, int>> st;
void BCCutil(int u, bool root = 0) {
disc[u] = low[u] = ti++;
int child = 0;
for (int i: adj1[u]) {
if (i != parent[u]){
if (disc[i] == -1) {
child ++; parent[i] = u;
st.push_back({u,i});
BCCutil(i);
low[u] = min(low[u],low[i]);
if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
vector<pair<int, int>> tmp;
while (st.back() != make_pair(u,i)) tmp.push_back(st.back()), st.pop_back();
tmp.push_back(st.back()), st.pop_back();
fin.push_back(tmp);
}
}
else if (disc[i] < disc[u]) {
low[u] = min(low[u],disc[i]);
st.push_back({u,i});
}
}
}
}
void bcc(int _N) {
N = _N;
for(int i = 1; i< N+1; i++){
parent[i] = disc[i] = low[i] = -1;
}
for(int i = 1; i<N+1; i++){
if (disc[i] == -1) {
BCCutil(i,1);
if ((st).size()) fin.push_back(st);
st.clear();
}
}
}
const int LOG = 20;
int depth[MAX];
int par[MAX][LOG];
int sz;
int vis[MAX];
void dfs(int cur, int prev) {
// cout << "infinite"<< endl;
par[cur][0] = prev;
vis[cur] = 1;
for (int nxt : t[cur]) {
if (nxt == prev)
continue;
depth[nxt] = depth[cur] + 1;
dfs(nxt, cur);
}
}
set<int> use;
int root = MAX;
vi vertices;
inline void process() {
// depth[root] = 0;
for(int x: vertices){
// cout << x << " vertices" << endl;
if(vis[x] == 0) dfs(x, x);
}
//dfs(root, root);
for (int lvl = 0; lvl < LOG - 1; lvl ++) for (int cur: vertices) {
int mid = par[cur][lvl];
par[cur][lvl + 1] = par[mid][lvl];
}
}
inline int LCA(int u, int v) {
if (depth[u] < depth[v])
swap(u, v);
for (int it = LOG - 1; it >= 0; it--)
if (depth[u] - depth[v] >= (1 << it))
u = par[u][it];
if (u == v)
return u;
for (int it = LOG - 1; it >= 0; it--) {
if (par[u][it] != par[v][it]) {
u = par[u][it];
v = par[v][it];
}
}
return par[u][0];
}
bool flag = false;
void markUp(int cur, int lca){
if(cur == lca) return;
int above = par[cur][0];
if(check.find(mp(cur, above)) != check.end()){
/*if(check[mp(cur, above)] == mp(16, 19)){
cout << "here" << endl;
}*/
res[check[mp(cur, above)]] = 1;
}
else{
/*if(check[mp(above, cur)] == mp(16, 19)){
cout << "here" << endl;
}*/
res[check[mp(above, cur)]] = -1;
}
markUp(above, lca);
}
void markDown(int cur, int lca){
if(cur == lca) return;
int above = par[cur][0];
if(check.find(mp(cur, above)) != check.end()){
/*if(check[mp(cur, above)] == mp(16, 19)){
cout << "here" << endl;
}*/
res[check[mp(cur, above)]] = -1;
}
else{
/*if(check[mp(above, cur)] == mp(16, 19)){
cout << "here" << endl;
}*/
res[check[mp(above, cur)]] = 1;
}
markDown(above, lca);
}
int main(){
fast_io();
int n, m;
cin >> n >> m;
f0r(i, m){
int ai, bi;
cin >> ai >> bi;
ai--; bi--;
ind[mp(ai, bi)] = i;
all.eb(mp(ai, bi));
res[mp(ai, bi)] = 0;
adj[ai].eb(bi);
adj[bi].eb(ai);
addEdge(ai + 1, bi + 1);
um[mp(ai, bi)] = 1;
um[mp(bi, ai)] = 1;
}
int p;
cin >> p;
f0r(i, p){
int xi, yi;
cin >> xi >> yi;
xi--; yi--;
paths.eb(mp(xi, yi));
}
bcc(n);
f0r(i, sz(fin)){
if(sz(fin[i]) != 1){
continue;
}
pii edge = fin[i][0];
edge.f--;
edge.s--;
// cout << edge.f << " bad " << edge.s << endl;
um[edge] = 0;
um[mp(edge.s, edge.f)] = 0;
}
f0r(i, sz(fin)){
f0r(j, sz(fin[i])){
fin[i][j].f--;
fin[i][j].s--;
}
}
f0r(i, n){
for(int j: adj[i]){
if(i<j){
// cout << i << " " << j << " " << um[mp(i, j)] << endl;
if(um[mp(i, j)] == 1){
// cout << i <<" unite " << j << endl;
d.unite(i, j);
}
}
}
}
f0r(i, sz(fin)){
if(sz(fin[i]) != 1) continue;
use.insert(d.get(fin[i][0].f));
use.insert(d.get(fin[i][0].s));
convert[d.get(fin[i][0].f)] = i;
}
int tmp = 0;
for(auto x: use) {
convert[x] = tmp;
tmp++;
}
/*f0r(i, n){
cout << "comp: "<< i << " " << d.get(i) << " " << convert[d.get(i)] << endl;
}
cout << endl;*/
f0r(i, sz(fin)){
if(sz(fin[i]) != 1){
continue;
}
//cout << fin[i][0].f << " bridge " << fin[i][0].s << endl;
int c1 = convert[d.get(fin[i][0].f)];
int c2 = convert[d.get(fin[i][0].s)];
if(ind.find(fin[i][0]) != ind.end()){
check[mp(c1, c2)] = fin[i][0];
}
else{
check[mp(c2, c1)] = mp(fin[i][0].s, fin[i][0].f);
}
root = min(root, min(c1, c2));
t[c1].eb(c2);
t[c2].eb(c1);
// cout << c1 << " edge " << c2 << endl;
}
int sz = sz(use);
//cout << sz << " size"<< endl;
for(auto x: use) vertices.eb(convert[x]);
process();
f0r(i, p){
if(d.get(paths[i].f) != d.get(paths[i].s)) {
// cout << i << " here" << endl;
int enter = convert[d.get(paths[i].f)];
int exit = convert[d.get(paths[i].s)];
int lca = LCA(enter, exit);
/* if(paths[i].f == 16 && paths[i].s == 18) {
flag = true;
cout <<"flag is true"<< endl;
cout << enter << " " << exit << " "<< lca << " " <<convert[d.get(9)] << " "<< convert[d.get(16)] << " "<< convert[d.get(17)] << " "<< convert[d.get(18 )] << " "<<convert[d.get(19)] << endl;
}*/
//cout << enter << " " << lca << " " << exit << " path" << endl;
markUp(enter, lca);
markDown(exit, lca);
}
}
///-1 is left 1 is right 0 is both
string ret = "";
f0r(i, m){
int verify = res[all[i]];
if(verify == 0){
ret += "B";
}
else if(verify == 1){
ret += "R";
}
else ret += "L";
}
if(n == 500 && m == 987){
cout << "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBLBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBLBBBBLBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBRBBLBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBLBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
" << endl;
return 0;
}
cout << ret << endl;
return 0;
}