Submission #1263740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263740		hungeazy	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	109 ms	46664 KiB

oneway

/*
* @Author: hungeazy
* @Date:   2025-08-17 08:35:35
* @Last Modified by:   hungeazy
* @Last Modified time: 2025-08-25 23:33:12
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
// #pragma GCC optimize("O3")  
// #pragma GCC optimize("unroll-loops")  
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
using namespace std;
using namespace __gnu_pbds; 
bool M1;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ll long long 
#define ull unsigned long long
#define sz(x) x.size()
#define sqr(x) (1LL * (x) * (x))
#define all(x) x.begin(), x.end()
#define fill(f,x) memset(f,x,sizeof(f))
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define debug(x) cout << #x << " = " << x << '\n'
#define ii pair<int,int>
#define iii pair<int,ii>
#define di pair<ii,ii>
#define vi vector<int>
#define vii vector<ii>
#define mii map<int,int>
#define fi first
#define se second
#define pb push_back
#define MOD 1000000007
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define MASK(i) (1LL << (i))
#define c_bit(i) __builtin_popcountll(i)
#define BIT(x,i) ((x) & MASK(i))
#define SET_ON(x,i) ((x) | MASK(i))
#define SET_OFF(x,i) ((x) & ~MASK(i))
#define oo 1e18
#define name "WAY"
#define endl '\n'
#define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
#define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
const int N = (int)1e5+10;
int n,m,p,x[N],y[N];
ii edge[N];
vii g[N];

namespace hungeazy {

	int d[N],low[N],cnt=0,sccId[N],tplt=0;
	bool in[N],check[N];
	int h[N],par[N][20],lo[N],needUp[N],needDown[N];
	stack<int> s;
	vii G[N];
	char ans[N];

	void Tarjan(int u, int p)
	{
		low[u] = d[u] = ++cnt;
		s.push(u);
		for (auto [v,id] : g[u])
			if (id != p and !in[v])
			{
				if (d[v]) minimize(low[u],d[v]);
				else  
				{
					Tarjan(v,id);
					minimize(low[u],low[v]);
				}
			}
		if (low[u] == d[u])
		{
			int v;
			tplt++;
			do {
				v = s.top();
				s.pop();
				sccId[v] = tplt;
				in[v] = true;
			} while (v != u);
		}
	}

	void DFS(int u, int p)
	{
		for (auto [v,id] : G[u])
			if (v != p)
			{
				h[v] = h[u]+1;
				par[v][0] = u;
				DFS(v,u);
			}
	}

	void init()
	{
		lo[1] = 0;
		FOR(i,2,N-10) lo[i] = lo[i/2]+1;
		FOR(j,1,lo[tplt])
			FOR(i,1,tplt) par[i][j] = par[par[i][j-1]][j-1];
	}

	int LCA(int x, int y)
	{
		if (h[x] < h[y]) swap(x,y);
		int z = lo[tplt];
		FOD(i,z,0)
			if (h[x]-h[y] >= MASK(i)) x = par[x][i];
		if (x == y) return x;
		FOD(i,z,0)
			if (par[x][i] != par[y][i])
			{
				x = par[x][i];
				y = par[y][i];
			}
		return par[x][0];
	}

	void solve(void)
	{
		FOR(i,1,n)
			if (!d[i]) Tarjan(i,-1);
		FOR(i,1,m)
		{
			auto [u,v] = edge[i];
			u = sccId[u], v = sccId[v];
			if (u != v)
			{
				G[u].pb({v,i}); 
				G[v].pb({u,i});
			}
		}
		DFS(1,-1);
		init();
		FOR(i,1,p)
		{
			int u = sccId[x[i]], v = sccId[y[i]];
			if (u == v) continue;
			int lca = LCA(u,v);
			needUp[u]++; needUp[lca]--;
			needDown[v]++; needDown[lca]--;
		}
		FOR(i,1,m) ans[i] = 'B';
		FOR(root,1,tplt)
		{
			if (check[root]) continue;
			stack<tuple<int,int,int>> st;
			st.push({root,0,0});
			while (!st.empty())
			{
				auto [u,par,state] = st.top();
				st.pop();
				if (!state)
				{
					if (check[u]) continue;
					check[u] = true;
					st.push({u,par,1});
					for (auto [v,id] : G[u])
						if (v != par)
							st.push({v,u,0});
				}
				else  
				{
					for (auto [v,id] : G[u])
						if (v != par)
						{
							needUp[u] += needUp[v];
							needDown[u] += needDown[v];
							int up = needUp[v], down = needDown[v];
							if (up > 0 and down > 0) continue;
							if (up > 0)
							{
								auto [U,V] = edge[id];
								U = sccId[U], V = sccId[V];
								if (U == v and V == u) ans[id] = 'R';
								else ans[id] = 'L';
							}
							else if (down > 0)
							{
								auto [U,V] = edge[id];
								U = sccId[U], V = sccId[V];
								if (U == u and V == v) ans[id] = 'R';
								else ans[id] = 'L';
							}
							else ans[id] = 'B';
						}
				}
			}
		}
		FOR(i,1,m) cout << ans[i];
	}
	
}

bool M2;
signed main()
{
    fast;
    if (fopen(name".inp","r"))
    {
    	freopen(name".inp","r",stdin);
    	freopen(name".out","w",stdout);
    }
    cin >> n >> m;
    FOR(i,1,m)
    {
    	int u,v;
    	cin >> u >> v;
    	edge[i] = {u,v};
    	g[u].pb({v,i}); g[v].pb({u,i});
    }
    cin >> p;
    FOR(i,1,p) cin >> x[i] >> y[i];
    hungeazy::solve();
    time();
    memory();
    return 0;
}
// ██░ ██  █    ██  ███▄    █   ▄████
//▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
//▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
//░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
//░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
// ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
// ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
// ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
// ░  ░  ░   ░              ░       ░

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:211:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:212:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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