Submission #917465

#	Time	Username	Problem	Language	Result	Execution time	Memory
917465		pan	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	13660 KiB

oneway

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
ll n, m, x,y, label = -1, q;
vector<ll> ans;
vector<pi> adj[100005];
vector<pi> treeadj[100005];
vector<pi> backadj[100005];
bool tree[100005];
vector<pi> edges;
vector<pi> city;
bool visited[100005];
ll depth[100005];
ll up[100005], down[100005], dp[100005];
ll bup[100005], bdown[100005], bdp[100005];
int lg(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

ll k, maxr;
vector<vector<pi > >rmq;
ll fa[100005];
vector<pi> arr;

void dfs1(ll p, ll node) // euler path
{
	label++;
	fa[node] = label;
	arr.pb(mp(depth[node], node));
	for (pi u: treeadj[node])
	{
		if (u.f==p) continue;
		depth[u.f] = depth[node]+1;
		dfs1(node, u.f);
		label++;
		arr.pb(mp(depth[node], node));
	}

}

void initrmq()
{
	maxr = arr.size();
	k = lg(maxr);
	rmq.assign(k+5, vector<pi> (maxr));
	rmq[0] = arr;
	for (ll i=1; i<=k; ++i)
	{
		for (ll j=0; j+ (1<<i) < maxr; ++j)
		{
			if (rmq[i-1][j].f < rmq[i-1][j + (1 << (i - 1))].f)
			{
				rmq[i][j] = rmq[i-1][j];
			}
			else
			{
				rmq[i][j] = rmq[i-1][j + (1 << (i - 1))];
			}
			
		}
	}
}

ll lca(ll node1, ll node2)
{
	ll l = fa[node1], r = fa[node2];
	if (l>r) swap(l,r);
	ll i = lg(r-l+1);
	if (rmq[i][l] < rmq[i][r - (1 << i) + 1])
	{
		return rmq[i][l].s;
	}
	else
	{
		return rmq[i][r - (1 << i) + 1].s;
	}
}

void dfs(ll p, ll from)
{
	//show(from);
	visited[from]  = true;
	for (pi u: adj[from])
	{
		if (u.f==p) continue;
		if (!visited[u.f])
		{
			tree[u.s] = true;
			treeadj[from].pb(u);
			treeadj[u.f].pb(mp(from, u.s));
			dfs(from, u.f);
		}

	}
}
void mark(ll p, ll node, ll label)
{
	ll counter = 0;
	ll bcounter = 0;
	for (pi u: treeadj[node]) 
	{
		if (u.f==p) continue;
		mark(node, u.f, label);
		if (dp[u.f]>0 && bdp[u.f]==0) ans[u.s] = label;
		counter+=dp[u.f];
		bcounter+= bdp[u.f];
	}
	counter+=up[node] - down[node];
	dp[node]  = counter;
	for (pi u: backadj[node])
	{
		//show(u.f);
		if (lca(u.f, node)==node) bcounter--;
		else bcounter++;
	}
	bdp[node] = bcounter;
	//show3(node, dp[node], bdp[node]);
		
}
int main()
{
	input(n); input(m);
	ans.resize(m); edges.resize(m);
	for (ll i=0; i<m; ++i) 
	{
		cin >> x >> y;
		x--;
		y--;
		adj[x].pb(mp(y, i));
		adj[y].pb(mp(x, i));
		edges[i] = mp(x,y);
	}
	dfs(-1, 0);
	depth[0] = 0;
	dfs1(-1, 0);
	initrmq();
	for (ll i=0; i<m; ++i)
	{
		if (!tree[i])
		{
			backadj[edges[i].f].pb(mp(edges[i].s, i));
			backadj[edges[i].s].pb(mp(edges[i].f, i));
		}
	}
	cin >> q;
	city.resize(q);
	for (ll i=0; i<q; ++i) {cin >> city[i].f >> city[i].s; city[i].f--; city[i].s--;}
	memset(up, 0, sizeof up);memset(down, 0, sizeof down);memset(dp, 0, sizeof dp);
	memset(up, 0, sizeof bup);memset(down, 0, sizeof bdown);memset(dp, 0, sizeof bdp);
	for (ll i=0; i<q; ++i)
	{
		ll mid = lca(city[i].f, city[i].s);
		if (mid==city[i].f) continue;
		up[city[i].f]++;
		down[mid]++;
	}
	//for (ll i=0;i<n; ++i) show3(i, up[i], down[i]);
	//for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) show3(i+1 ,j+1 , lca(i,j)+1);
	mark(-1, 0, 1); // go up
	memset(up, 0, sizeof up);memset(down, 0, sizeof down);memset(dp, 0, sizeof dp);
	memset(up, 0, sizeof bup);memset(down, 0, sizeof bdown);memset(dp, 0, sizeof bdp);
	for (ll i=0; i<q; ++i)
	{
		ll mid = lca(city[i].f, city[i].s);
		if (mid==city[i].s) continue;
		up[city[i].s]++;
		down[mid]++;
	}
	mark(-1, 0, 2);// go down
	for (ll i=0; i<m; ++i)
	{
		ll mid =  lca(edges[i].f, edges[i].s);
		if (ans[i]==0) cout << 'B';
		else if ((ans[i]==1 && mid!=edges[i].f) || (ans[i]==2 && mid!=edges[i].s)) cout << 'R';
		else  cout << 'L';
	}
	cout << endl;
	
	
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
oneway.cpp:142:2: note: in expansion of macro 'input'
  142 |  input(n); input(m);
      |  ^~~~~
oneway.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
oneway.cpp:142:12: note: in expansion of macro 'input'
  142 |  input(n); input(m);
      |            ^~~~~

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