제출 #1338467

#제출 시각아이디문제언어결과실행 시간메모리
1338467rexdinoOne-Way Streets (CEOI17_oneway)C++20
0 / 100
20 ms4804 KiB
#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define REP(i, a, b) for(int i=(a); i>=(b); --i)
#define umax(x, y) x = max(x, (y))
#define umin(x, y) x = min(x, (y))
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define sz(v) (int)(v).size()
#define ALL(v) (v).begin(),(v).end()
using namespace std;
    
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const ll INF = 1e18;

// Author: rexdino
int n, m, p;
pii edges[N];
vector<int> adj[N];
int tin[N], tout[N], Timer, par[22][N], low[N], h[N];
int id[N], cnt, dp[N], up[N], down[N];
bool del[N];
char ans[N];

void dfs(int u){
	tin[u] = low[u] = ++Timer;
	for (int id : adj[u]){
		int v = edges[id].fi + edges[id].se - u;
		if (v != par[0][u]){	
			if (!tin[v]){
				par[0][v] = u;
				dfs(v);
				umin(low[u], low[v]);
				dp[u] += dp[v];
				up[u] += up[v];
				down[u] += down[v];

				if (low[v] <= tin[u]) continue;

				cerr << id << ": " << u << " " << v << ": " << up[v] << " " << down[v] << "\n";
				// cerr << u << " " << v << "\n";
				if (up[v]) {
					if (edges[id].fi == u) ans[id] = 'L';
					else ans[id] = 'R';
				} else if (down[v]) {
					if (edges[id].fi == u) ans[id] = 'R';
					else ans[id] = 'L';
				} else ans[id] = 'B';

			} else umin(low[u], tin[v]);
		}
	}
	tout[u] = Timer;
}

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

int lca(int u, int v){
	if (isAnc(u, v)) return u;
	if (isAnc(v, u)) return v;

	REP(i, 20, 0) if (!isAnc(par[i][u], v)) u = par[i][u];
	return par[0][u];
}

void solve(){
	cin >> n >> m;
	FOR(i, 1, m){
		int u, v;
		cin >> u >> v;
		edges[i] = {u, v};
		adj[u].push_back(i);
		adj[v].push_back(i);
	}

	FOR(i, 1, n) if (!tin[i]) {
		par[0][i] = i;
		dfs(i);
	}

	FOR(i, 1, 20) FOR(u, 1, n) par[i][u] = par[i - 1][par[i - 1][u]];

	cin >> p;
	while(p--){
		int x, y;
		cin >> x >> y;

		int z = lca(x, y);
		cerr << "lca " << x << " " << y << ": " << z << "\n";
		up[x]++;
		up[z]--;
		down[y]++;
		down[z]--;
	}

	cerr << "\n";

	Timer = 0;
	memset(tin, 0, sizeof tin);
	FOR(i, 1, n) if (!tin[i]) dfs(i);

	FOR(i, 1, m){
		if (ans[i] != 'R' && ans[i] != 'L') ans[i] = 'B';
		cout << ans[i];
	}


}

signed main(){
    #define NAME "main"
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    while(t--) solve();

    // cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
    return 0;
}

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

oneway.cpp: In function 'int main()':
oneway.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...