oj.uz

Submission #111001

# Submission time Handle Problem Language Result Execution time Memory
111001 2019-05-13T14:11:18 Z dndhk One-Way Streets (CEOI17_oneway) C++14
100 / 100
 385 ms 33624 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2908 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 5 ms 2816 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2908 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 5 ms 2816 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 97 ms 10448 KB Output is correct
12 Correct 70 ms 12000 KB Output is correct
13 Correct 113 ms 17512 KB Output is correct
14 Correct 174 ms 26712 KB Output is correct
15 Correct 198 ms 27608 KB Output is correct
16 Correct 368 ms 27736 KB Output is correct
17 Correct 239 ms 28636 KB Output is correct
18 Correct 370 ms 27740 KB Output is correct
19 Correct 244 ms 29400 KB Output is correct
20 Correct 84 ms 16740 KB Output is correct
21 Correct 78 ms 16564 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2908 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 5 ms 2816 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 97 ms 10448 KB Output is correct
12 Correct 70 ms 12000 KB Output is correct
13 Correct 113 ms 17512 KB Output is correct
14 Correct 174 ms 26712 KB Output is correct
15 Correct 198 ms 27608 KB Output is correct
16 Correct 368 ms 27736 KB Output is correct
17 Correct 239 ms 28636 KB Output is correct
18 Correct 370 ms 27740 KB Output is correct
19 Correct 244 ms 29400 KB Output is correct
20 Correct 84 ms 16740 KB Output is correct
21 Correct 78 ms 16564 KB Output is correct
22 Correct 313 ms 29416 KB Output is correct
23 Correct 351 ms 30928 KB Output is correct
24 Correct 385 ms 30812 KB Output is correct
25 Correct 342 ms 33624 KB Output is correct
26 Correct 298 ms 31452 KB Output is correct
27 Correct 314 ms 30852 KB Output is correct
28 Correct 58 ms 7148 KB Output is correct
29 Correct 153 ms 19488 KB Output is correct
30 Correct 172 ms 19632 KB Output is correct
31 Correct 164 ms 19808 KB Output is correct
32 Correct 195 ms 22168 KB Output is correct