oj.uz

답안 #490952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490952 2021-11-30T01:48:38 Z hohohaha One-Way Streets (CEOI17_oneway) C++14
0 / 100
 4 ms 7372 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int maxn = 1e5 + 1; 

int n, m, q; 

int low[maxn], in[maxn], inptr; 

bool isbr[maxn]; 

vector<ii> g[maxn]; 

set<ii> S[maxn]; 

ii last[maxn]; 

void dfs(int i, int pe, int p) { 

	low[i] = in[i] = ++inptr; 

	for(ii t: g[i]) { 
		int j=  t.fi, id = t.se; 
		if(!in[j]) {
			dfs(j, id, i); 
			low[i] = min(low[i], low[j]); 
			
			if(S[i].size() < S[j].size()) S[i].swap(S[j]); 
			
			for(ii t: S[j]) { 
				if(S[i].count({t.fi, t.se ^ 1})) { 
					S[i].erase({t.fi, t.se ^ 1}); 
				}
				else { 
					S[i].insert(t); 
				}
			}
						
		}
		else if(id - pe and low[j] < low[i]) { 
			low[i] = min(low[i], in[j]);
		}
	}
	if(low[i] >= in[i]) {
		if(S[i].size() and S[i].begin() -> se == 0) last[pe] = {i, p}; 
		else if(S[i].size() and S[i].begin() ->se == 1) last[pe] = {p, i};
	}
}
void solve() { 
	cin >> n >> m; 
	fori(i, 1, m) { 
		int u, v; cin >> u >> v; 
		g[u].eb(v, i); 
		g[v].eb(u, i); 
	}
	
	cin >> q; 
	fori(i,1, q){ 
		int u,v; cin >> u >> v; 
		S[u].em(i, 0); 
		S[v].em(i, 1); 
	}
	dfs(1, -1, 1); 
	fori(i,1, m) { 
		if(!last[i].fi) cout << "B";
	 	else if(last[i].fi <last[i].se) cout << "L"; 
	 	else cout << "R"; 
	 }
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -