Submission #695607

#	Time	Username	Problem	Language	Result	Execution time	Memory
695607		KiaRez	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	8 ms	5872 KiB

oneway

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define DASH                                   "---------"
#define UNDERLINE                              "_________"
#define all(x)                                 (x).begin(),(x).end()
#define FORD(i, s, e)                          for(int i=s; i>=e; --i)
#define FOR(i, s, e)                           for(int i=s; i<=e; ++i)
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int _N = 232323, _LG=131072, _lg=18;
const ll _MOD = 1e9+7; // 998244353

ll getmod(ll a, ll mod=_MOD)                   {return (a+3*mod)%mod;}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}

int n, m, p, pref[_N][2], par[_N][_lg], low[_N], h[_N], mark[_N], ANS[_N];
vector<pii> adj[_N];
pii E[_N];

void addEdge(int ind) {
	int v,u;
	cin>>v>>u;
	adj[v].pb({u, ind});
	adj[u].pb({v, ind});
	E[ind]={v, u};
}

void dfs(int v=1, int ind=0) {
	low[v]=1e9, mark[v]=1;
	FOR(i,1,_lg-1) {par[v][i]=par[par[v][i-1]][i-1];}
	for(auto it2 : adj[v]) {
		auto it = it2.F;
		if(mark[it]==0) {
			par[it][0]=v, h[it]=h[v]+1;
			dfs(it, it2.S);
			low[v]=min(low[it], low[v]);
		} else if (it2.S!=ind) {
			low[v]=min(h[it], low[v]);
		}
	}
}

int getPar(int v, int dist) {
	while(dist>0) {
		v=par[v][(int)log2(dist&-dist)];
		dist-=(dist&-dist);
	}
	return v;
}
 
int getLCA(int v, int u) {
	if(h[v]>h[u]) {swap(v,u);}
	u=getPar(u, h[u]-h[v]);
	if(v==u) {return v;}
	FORD(i,_lg-1, 0) {
		if(par[v][i]!=par[u][i]) {v=par[v][i], u=par[u][i];}
	}
	return par[v][0];
}

void partial(int v=1) {
	mark[v]=1;
	for(auto it : adj[v]) {
		if(!mark[it.F]) {
			partial(it.F);
			pref[v][0]+=pref[it.F][0];
			pref[v][1]+=pref[it.F][1];
			if (low[it.F]>h[v] && (pref[it.F][0]!=0||pref[it.F][1]!=0)) {
				ANS[it.S] = (pref[it.F][0]!=0 ? (E[it.S].F==it.F ? 1 : -1) : (E[it.S].F==v ? 1 : -1));
			}
		}
	}
}

int main () {
	ios;

	file_io("oneway.01.01.in", "out.txt");

	cin>>n>>m; h[1]=1;
	FOR(i,1,m) {addEdge(i);}
	FOR(i,1,n) {
		if(!mark[i]) {
			dfs(i, 0);
		}
	}
	fill(mark, mark+n+2, 0);
	cin>>p;
	FOR(i,1,p) {
		int v,u,lca;
		cin>>v>>u; // 0 -> up | 1 -> down
		lca=getLCA(v,u);
		if (lca==v) {
			pref[u][1]++;pref[v][1]--;
		} else if (lca==u) {
			pref[v][0]++;pref[u][0]--;
		} else {
			pref[v][0]++;pref[u][1]++;pref[lca][0]--;pref[lca][1]--;
		}
	}
	FOR(i,1,n) {
		if(!mark[i]) {
			partial(i);
		}
	}

	// FOR(i,1,n) {
	// 	cout<<par[i][0]<<' ';
	// }
	// cout<<endl;

	FOR(i,1,m) {
		cout<<(ANS[i]==0 ? 'B' : (ANS[i]==1 ? 'R' : 'L'));
	}

	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:37:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | #define file_io(x,y)                        freopen(x, "r", stdin); freopen(y, "w", stdout);
      |                                             ~~~~~~~^~~~~~~~~~~~~~~
oneway.cpp:109:2: note: in expansion of macro 'file_io'
  109 |  file_io("oneway.01.01.in", "out.txt");
      |  ^~~~~~~
oneway.cpp:37:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | #define file_io(x,y)                        freopen(x, "r", stdin); freopen(y, "w", stdout);
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:109:2: note: in expansion of macro 'file_io'
  109 |  file_io("oneway.01.01.in", "out.txt");
      |  ^~~~~~~

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