oj.uz

Submission #110999

# Submission time Handle Problem Language Result Execution time Memory
110999 2019-05-13T14:10:45 Z dndhk One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 31708 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){
	s1.pb({x, y});
	//u1(0, 1, cntn, x, y);
}

void update2(int x, int y){
	s2.pb({x, y});
	//u2(0, 1, cntn, x, y);
}

int max1(int x, int y){
	int ret = 0;
	for(int i=0; i<s1.size(); i++){
		if(s1[i].first>=x && s1[i].first<=y){
			ret = max(ret, s1[i].second);
		}
	}
	return ret;
	//return mx1(0, 1, cntn, x, y);
}

int min1(int x, int y){
	int ret = INF;
	for(int i=0; i<s1.size(); i++){
		if(s1[i].first>=x && s1[i].first<=y){
			ret = min(ret, s1[i].second);
		}
	}
	return ret;
	//return mn1(0, 1, cntn, x, y);
}

int max2(int x, int y){
	int ret = 0;
	for(int i=0; i<s2.size(); i++){
		if(s2[i].first>=x && s2[i].first<=y){
			ret = max(ret, s2[i].second);
		}
	}
	return ret;
	//return mx2(0, 1, cntn, x, y);
}

int min2(int x, int y){
	int ret = INF;
	for(int i=0; i<s2.size(); i++){
		if(s2[i].first>=x && s2[i].first<=y){
			ret = min(ret, s2[i].second);
		}
	}
	return ret;
	//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 max1(int, int)':
oneway.cpp:141:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s1.size(); i++){
               ~^~~~~~~~~~
oneway.cpp: In function 'int min1(int, int)':
oneway.cpp:152:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s1.size(); i++){
               ~^~~~~~~~~~
oneway.cpp: In function 'int max2(int, int)':
oneway.cpp:163:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s2.size(); i++){
               ~^~~~~~~~~~
oneway.cpp: In function 'int min2(int, int)':
oneway.cpp:174:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s2.size(); i++){
               ~^~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:187: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:190: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:194:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &P);
  ~~~~~^~~~~~~~~~
oneway.cpp:197: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 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 7 ms 2944 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 6 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 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 7 ms 2944 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 82 ms 11560 KB Output is correct
12 Correct 91 ms 13116 KB Output is correct
13 Correct 120 ms 18764 KB Output is correct
14 Correct 179 ms 27844 KB Output is correct
15 Correct 193 ms 28816 KB Output is correct
16 Correct 121 ms 28892 KB Output is correct
17 Correct 164 ms 29788 KB Output is correct
18 Correct 210 ms 28944 KB Output is correct
19 Correct 154 ms 30432 KB Output is correct
20 Correct 99 ms 17904 KB Output is correct
21 Correct 88 ms 17652 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 7 ms 2944 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 82 ms 11560 KB Output is correct
12 Correct 91 ms 13116 KB Output is correct
13 Correct 120 ms 18764 KB Output is correct
14 Correct 179 ms 27844 KB Output is correct
15 Correct 193 ms 28816 KB Output is correct
16 Correct 121 ms 28892 KB Output is correct
17 Correct 164 ms 29788 KB Output is correct
18 Correct 210 ms 28944 KB Output is correct
19 Correct 154 ms 30432 KB Output is correct
20 Correct 99 ms 17904 KB Output is correct
21 Correct 88 ms 17652 KB Output is correct
22 Execution timed out 3083 ms 31708 KB Time limit exceeded
23 Halted 0 ms 0 KB -