Submission #1115097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115097		Sunbae	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	4 ms	11856 KiB

oneway

#include <bits/stdc++.h>
#define z exit(0)
#define mp make_pair
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
const int N = 100000;
vector<int> g[N], tree[N], st[N], ed[N];
set<pii> bridge, ok;
map<pii,int> cnt;
int tin[N], low[N], rt[N], up[N], ti, sz;
set<int> ds;
pii I[N];
void dfs(int u, int p){
	low[u] = tin[u] = ti++;
	for(int v: g[u]){
		if(v != p){
			if(tin[v] == -1){
				tree[u].push_back(v);
				dfs(v, u); 
				low[u] = min(low[u], low[v]);
				int x = min(u, v), y = max(u, v);
				if(low[v] > tin[u] && cnt[mp(x, y)] == 1){
					bridge.emplace(x, y);
				}
			}else{
				low[u] = min(low[u], tin[v]);
			}
		}
	}
}
void efs(int u){
	for(int v: tree[u]) up[v] = u, efs(v);
	for(int i: st[u]) ds.insert(i);
	for(int i: ed[u]) if(ds.find(i) != ds.end()) ds.erase(i);
	if(up[u] != -1 && !ds.empty()) ok.emplace(up[u], u);
}
signed main(){
	int n, m; scanf("%d %d", &n, &m);
	for(int i = 0, u, v; i<m; ++i){
		scanf("%d %d", &u, &v); --u; --v;
		I[i] = {u, v};
		if(u > v) swap(u, v);
		if(!cnt[mp(u, v)]){
			g[u].push_back(v); g[v].push_back(u);
		}
		++cnt[mp(u, v)];
	}
	memset(tin, -1, sizeof(tin));
	for(int i = 0; i<n; ++i){
		if(tin[i] == -1) dfs(rt[sz++] = i, -1);
	}
	int q; scanf("%d", &q);
	for(int i = 0, u, v; i<q; ++i){
		scanf("%d %d", &u, &v); --u; --v;
		st[u].push_back(i); ed[v].push_back(i);
	}			
	memset(up, -1, sizeof(up));
	for(int i = 0; i<sz; ++i) efs(rt[i]);
	for(int i = 0; i<m; ++i){
		int u = I[i].F, v = I[i].S;
		if(bridge.find(mp(min(u, v), max(u, v))) == bridge.end()){
			printf("B"); continue;
		}
		char ch;
		if(u == up[v]){
			ch = 'R';
			if(ok.find(mp(u, v)) != ok.end()) ch = 'L';
		}else if(v == up[u]){
			ch = 'L';
			if(ok.find(mp(v, u)) != ok.end()) ch = 'R';
		}
		printf("%c", ch);
	}	
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:40:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d %d", &u, &v); --u; --v;
      |   ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
oneway.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d %d", &u, &v); --u; --v;
      |   ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:74:9: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |   printf("%c", ch);
      |   ~~~~~~^~~~~~~~~~

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