Submission #1193621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193621		Bui_Quoc_Cuong	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	239 ms	35768 KiB

oneway

#include<bits/stdc++.h>
using namespace std; 
#define             ll  long long 
#define             db  double 
#define             vi  vector<int>
#define            str  string
#define             pb  push_back
#define            pii  pair<int,int>
#define            pll  pair<ll,ll>
#define            pli  pair<ll, int>
#define             mp  make_pair 
#define             fi  first 
#define             se  second
#define         UNI(A)  sort(ALL(A)),A.resize(unique(ALL(A))-A.begin()) 
#define     FOR(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    FORN(i,a,b)  for(int i=(int)(a);i<(int)(b);i++)
#define         ALL(a)  a.begin(),a.end()  
#define             LB  lower_bound
#define             UB  upper_bound 
#define            tct  template<class T1, class G2>
#define     BIT(msk,i)  (msk>>(i)&1)
#define        M(i)  (1ll<<(i))
#define          SZ(_)  (int)(_.size())
#define           btpc  __builtin_popcountll
#define            ctz  __builtin_ctzll 
ll lg(ll a){return __lg(a);}
ll sq(ll a){return a*a;}  
ll gcd(ll a,ll b){return __gcd(a,b);} 
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll rd(ll l , ll r ){return l+1LL*rand()*rand()%(r-l+1);}
#define prt(a,n) {FOR(_i,1,n)cout<<a[_i]<<" ";cout<<el;}
#define prv(a) {for(auto _v:a)cout<<_v<<" "; cout<<el;} 

tct bool maxi(T1 &a, const G2 b){if(a < b) {a = b; return true;} return false;}
tct bool mini(T1 &a, const G2 b){if(a > b) {a = b; return true;} return false;}

const int dx[] = {0,-1,0,1}; 
const int dy[] = {-1,0,1,0};

const int N = 2e5 +5, oo = 2e9, LG = __lg(N) + 1, CH = 26 ; 
const db PI = acos(-1), EPS = 1e-9;
const ll inf = 1e18, cs = 331, sm = 1e9+7; 

#define Hori "oneway"
bool mtt = 0;
int test = 1;  

int n, m, p;
struct Edges
{
	int u, v; 
} E[N];
int x[N], y[N];
char ans[N];

namespace sub3
{
	int low[N], num[N], sccID[N], timer, vis[N], scc;
	stack <int> st;
	vector <pii> adj[N];
	vector <int> ke[N];
	int P[N][LG], h[N], ID[N];

	void tarjan(int u, int oldID)
	{
		num[u] = low[u] = ++ timer;
		st.push(u);
		for(const pii &it : adj[u])
		{
			int v = it.fi, curID = it.se;
			if(curID == oldID || vis[v]) continue;
			if(num[v] > 0) mini(low[u], num[v]);
			else
			{
				tarjan(v, curID);
				mini(low[u], low[v]);
			}
		}
		if(low[u] == num[u])
		{
			int x;
			scc++;
			do 
			{
				x = st.top(); 
				vis[x] = 1;
				sccID[x] = scc;
				st.pop();
			} while(x != u);
		}
	}

	int sz[N], head[N], cur[N], pos[N], timeDFS, crt, par[N];

	void dfs_sz(int u)
	{
		sz[u] = vis[u] = 1;
		for(const int &v : ke[u])
		{
			if(vis[v]) continue;
			h[v] = h[u] + 1;
			par[v] = u;
			P[v][0] = u;
			dfs_sz(v);
			sz[u]+= sz[v];
		}
	}	

	void dfs_hld(int u)
	{
		vis[u] = 1;
		if(!head[crt]) head[crt] = u;
		pos[u] = ++timeDFS;
		cur[u] = crt;

		int nxt = 0;
		for(const int &v : ke[u])
		{
			if(vis[v] || v == par[u]) continue;
			if(sz[v] > sz[nxt]) nxt = v;
		}

		if(nxt) dfs_hld(nxt);

		for(const int &v : ke[u])
		{
			if(vis[v] || v == nxt || v == par[u]) continue;
			crt++;
			dfs_hld(v);
		}
	}

	int tree[4 * N], lazy[4 * N];

	void down(int id, int l, int r)
	{
		if(lazy[id] == 0) return;

		int mid = (l + r) >> 1;

		tree[id << 1] = (mid - l + 1) * lazy[id];
		tree[id << 1 | 1] = (r - mid) * lazy[id];

		lazy[id << 1] = lazy[id];
		lazy[id << 1 | 1] = lazy[id];

		lazy[id] = 0;
	}

	void update(int id, int l, int r, int u, int v, int val)
	{
		if(l > v || r < u) return;
		if(l >= u && r <= v)
		{
			tree[id] = (r - l + 1) * val;
			lazy[id] = val;
			return;
		}
		int mid = (l + r) >> 1;
		down(id, l, r);
		update(id << 1, l, mid, u, v, val);
		update(id << 1 | 1, mid + 1, r, u, v, val);
		tree[id] = tree[id << 1] + tree[id << 1 | 1];
	}	

	int get(int id, int l, int r, int u, int v)
	{
		if(l > v || r < u) return 0;
		if(l >= u && r <= v) return tree[id];
		down(id, l, r);
		int mid = (l + r) >> 1;
		return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
	}

	int LCA(int u, int v)
	{
		while(cur[u] != cur[v])
		{
			if(cur[u] > cur[v]) u = par[head[cur[u]]];
			else v = par[head[cur[v]]];
		}
		if(h[u] < h[v]) return u;
		else return v;
	}

	void upPath(int u, int v)
	{
		int p = LCA(u, v);	

		while(cur[u] != cur[p])
		{
			update(1, 1, scc, pos[head[cur[u]]], pos[u], 1);
			u = par[head[cur[u]]];
		}

		while(cur[v] != cur[p])
		{
			update(1, 1, scc, pos[head[cur[v]]], pos[v], 2);
			v = par[head[cur[v]]];
		}	

		if(pos[u] < pos[v])
		{
			update(1, 1, scc, pos[u] + 1, pos[v], 2);
		}
		if(pos[u] > pos[v])
		{
			update(1, 1, scc, pos[v] + 1, pos[u], 1);
		}	
	}

	int getPath(int u, int v)
	{
		int p = LCA(u, v);	
		int res = 0;
		while(cur[u] != cur[p])
		{
			res+= get(1, 1, scc, pos[head[cur[u]]], pos[u]);
			u = par[head[cur[u]]];
		}
		while(cur[v] != cur[p])
		{
			res+= get(1, 1, scc, pos[head[cur[v]]], pos[v]);
			v = par[head[cur[v]]];
		}	
		if(pos[u] < pos[v]) res+= get(1, 1, scc, pos[u] + 1, pos[v]);
		else if(pos[u] > pos[v]) res+= get(1, 1, scc, pos[v] + 1, pos[u]);
		return res;
	}

	void solve()
	{
		FOR(i, 1, m)
		{
			adj[E[i].u].pb({E[i].v, i});
			adj[E[i].v].pb({E[i].u, i});
		}	

		FOR(i, 1, n) if(num[i] == 0) tarjan(i, 0);

		FOR(i, 1, m)
		{
			int X = sccID[E[i].u], Y = sccID[E[i].v];
			if(X == Y) continue;
			ke[X].push_back(Y);
			ke[Y].push_back(X);
		}	

		FOR(i, 1, scc) vis[i] = 0;
		FOR(i, 1, scc) if(!vis[i]) dfs_sz(i);

		FOR(i, 1, scc) vis[i] = 0;
		FOR(i, 1, scc) if(!vis[i]) dfs_hld(i);	

		memset(ans, 'B', sizeof ans);
		FOR(i, 1, p) upPath(sccID[x[i]], sccID[y[i]]);

		FOR(i, 1, m)
		{
			int X = sccID[E[i].u], Y = sccID[E[i].v];
			if(X == Y) continue;
			int val = getPath(X, Y);
			if(val == 1)
			{
				if(X == P[Y][0]) ans[i] = 'L';
				else ans[i] = 'R';
			}	
			if(val == 2)
			{
				if(X == P[Y][0]) ans[i] = 'R';
				else ans[i] = 'L';
			}	
		}
		FOR(i, 1, m) cout << ans[i];
	}	
}

void process() 
{
	cin >> n >> m;
	FOR(i, 1, m) cin >> E[i].u >> E[i].v;
	cin >> p;	
	FOR(i, 1, p) cin >> x[i] >> y[i];
	sub3::solve();
}

signed main() 
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0)); 
    if(fopen(Hori".inp","r")) 
    {
        freopen(Hori".inp","r",stdin);
        freopen(Hori".out","w",stdout);
    }
    else if(fopen(".inp","r")) 
    {
        freopen(".inp","r",stdin); 
        freopen(".out","w",stdout);   
    }

    if(mtt) cin >> test;
    while(test--) process();

    cerr << "\nTime Elapsed : " << 0.001 * clock() << "s ";
}

Compilation message (stderr)

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

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