Submission #111001

#	Time	Username	Problem	Language	Result	Execution time	Memory
111001		dndhk	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	385 ms	33624 KiB

oneway

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 100000;

int N, M, P;
vector<int> gp[MAX_N+1];
vector<pii> edge;
vector<pii> edge2;

int num[MAX_N+1][2];
int cntn = 0;
int vst[MAX_N+1];
int p[MAX_N+1];
int up[MAX_N+1];
int lv[MAX_N+1];
bool chk[MAX_N+1];

void dfs(int x){
	int cnt = 1;
	vst[x] = true;
	up[x] = lv[x];
	num[x][0] = ++cntn;
	for(int i=0; i<gp[x].size(); i++){
		if(!vst[gp[x][i]]){
			p[gp[x][i]] = x;
			lv[gp[x][i]] = lv[x]+1;
			dfs(gp[x][i]);
			if(up[gp[x][i]]>lv[x]){
				chk[gp[x][i]] = true;
			}
			up[x] = min(up[x], up[gp[x][i]]);
		}else{
			if(cnt>0 && gp[x][i]==p[x])	{
				cnt--; continue;
			}
			up[x] = min(up[x], lv[gp[x][i]]);
		}
	}
	num[x][1] = ++cntn;
}

struct SEG{
	SEG(int l, int r, int mn, int mx) : l(l), r(r), mn(mn), mx(mx) {}
	int l, r;
	int mn, mx;
};
vector<SEG> seg1, seg2;

void init1(int idx, int s, int e){
	if(s==e)	return;
	seg1[idx].l = seg1.size();	seg1.pb({-1, -1, INF, 0});
	seg1[idx].r = seg1.size();	seg1.pb({-1, -1, INF, 0});
	init1(seg1[idx].l, s, (s+e)/2);
	init1(seg1[idx].r, (s+e)/2+1, e);
}

void init2(int idx, int s, int e){
	if(s==e)	return;
	seg2[idx].l = seg2.size();	seg2.pb({-1, -1, INF, 0});
	seg2[idx].r = seg2.size();	seg2.pb({-1, -1, INF, 0});
	init2(seg2[idx].l, s, (s+e)/2);
	init2(seg2[idx].r, (s+e)/2+1, e);
}

void u1(int idx, int s, int e, int x, int y){
	seg1[idx].mn = min(seg1[idx].mn, y);
	seg1[idx].mx = max(seg1[idx].mx, y);
	if(s==e)	return;
	int m = (s+e)/2;
	if(x<=m)	u1(seg1[idx].l, s, m, x, y);
	else	u1(seg1[idx].r, m+1, e, x, y);
}

void u2(int idx, int s, int e, int x, int y){
	seg2[idx].mn = min(seg2[idx].mn, y);
	seg2[idx].mx = max(seg2[idx].mx, y);
	if(s==e)	return;
	int m = (s+e)/2;
	if(x<=m)	u2(seg2[idx].l, s, m, x, y);
	else	u2(seg2[idx].r, m+1, e, x, y);
}

int mx1(int idx, int s, int e, int x, int y){
	if(x<=s && e<=y)	return seg1[idx].mx;
	if(x>e || s>y)	return 0;
	return max(mx1(seg1[idx].l, s, (s+e)/2, x, y), mx1(seg1[idx].r, (s+e)/2+1, e, x, y));
}

int mn1(int idx, int s, int e, int x, int y){
	if(x<=s && e<=y)	return seg1[idx].mn;
	if(x>e || s>y)	return INF;
	return min(mn1(seg1[idx].l, s, (s+e)/2, x, y), mn1(seg1[idx].r, (s+e)/2+1, e, x, y));
}
int mx2(int idx, int s, int e, int x, int y){
	if(x<=s && e<=y)	return seg2[idx].mx;
	if(x>e || s>y)	return 0;
	return max(mx2(seg2[idx].l, s, (s+e)/2, x, y), mx2(seg2[idx].r, (s+e)/2+1, e, x, y));
}
int mn2(int idx, int s, int e, int x, int y){
	if(x<=s && e<=y)	return seg2[idx].mn;
	if(x>e || s>y)	return INF;
	return min(mn2(seg2[idx].l, s, (s+e)/2, x, y), mn2(seg2[idx].r, (s+e)/2+1, e, x, y));
}


vector<pii> s1, s2;

void update1(int x, int y){u1(0, 1, cntn, x, y);
}

void update2(int x, int y){u2(0, 1, cntn, x, y);
}

int max1(int x, int y){return mx1(0, 1, cntn, x, y);
}

int min1(int x, int y){
	return mn1(0, 1, cntn, x, y);
}

int max2(int x, int y){return mx2(0, 1, cntn, x, y);
}

int min2(int x, int y){return mn2(0, 1, cntn, x, y);
}




int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		gp[x].pb(y); gp[y].pb(x);
		edge.pb({x, y});
	}
	scanf("%d", &P);
	for(int i=0; i<P; i++){
		int x, y;
		scanf("%d%d",&x, &y);
		edge2.pb({x, y});
	}
	lv[1] = 1;
	for(int i=1; i<=N; i++){
		if(!vst[i])	dfs(i);
	}
	seg1.pb({-1, -1, INF, 0});	seg2.pb({-1, -1, INF, 0});
	init1(0, 1, cntn); init2(0, 1, cntn);
	for(int i=0; i<P; i++){
		update1(num[edge2[i].first][0], num[edge2[i].second][0]);
		update2(num[edge2[i].second][0], num[edge2[i].first][0]);
	}
	for(int i=0; i<M; i++){
		bool swp = false;
		if(p[edge[i].first] == edge[i].second){
			swp = true;
			int tmp = edge[i].FI; edge[i].FI = edge[i].SE; edge[i].SE = tmp;
		}
		if(p[edge[i].second]!=edge[i].first || !chk[edge[i].second]){
			printf("B");
			continue;
		}
		int l = num[edge[i].second][0], r = num[edge[i].second][1];
		if(max1(l, r)>r || min1(l, r)<l){
			printf("%c", (swp?'R':'L'));
		}else if(max2(l, r)>r || min2(l, r)<l){
			printf("%c", (swp?'L':'R'));
		}else{
			printf("B");
		}
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int)':
oneway.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &P);
  ~~~~~^~~~~~~~~~
oneway.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x, &y);
   ~~~~~^~~~~~~~~~~~~~~

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