Submission #309532

#	Time	Username	Problem	Language	Result	Execution time	Memory
309532		bigg	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	315 ms	36468 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXK = 23;
int marc[MAXN], tin[MAXN], low[MAXN], comp[MAXN], T;
struct edge{
	int tipo;
	int u, v;
	void maketype(int mu, int mv, bool isont){
	//	printf("%d %d %d %d %d\n", mu, mv, isont,u, v );
		if(mu == 0){
			tipo = 3;
			return;
		}
		if(!isont){
			if(mu == u ) tipo = 1;
			else tipo = 2;
		}else{
			if(mu == comp[u]) tipo = 1;
			else tipo = 2;
		}
	}

}edges[MAXN];
vector<pair<int, int> > grafo[MAXN], grafosemponte[MAXN];
vector<int> bridge;


void makebridge( int id, int isbridge){
	if(!isbridge) edges[id].maketype(0,0,0);
	else{
		bridge.push_back(id);
	}
}

void dfsini(int x, int idp){
	marc[x] = 1;
	tin[x] = low[x] = ++T;
	for(int i = 0; i < grafo[x].size(); i++){
		int viz = grafo[x][i].first;
		int id = grafo[x][i].second;
		if(id == idp) continue;
		if(marc[viz]) low[x] = min(tin[viz], low[x]);
		else{
			dfsini(viz, id);
			makebridge(id, low[viz] > tin[x]);
			low[x] = min(low[x], low[viz]);
		}
	} 
}
int cmp;
void dfssec(int x){
	comp[x] = cmp;
	for(int i = 0; i < grafosemponte[x].size(); i++){
		int viz = grafosemponte[x][i].first;
		if(comp[viz]) continue;
		dfssec(viz);
	}
}

vector<pair<int, int> > tree[MAXN];
int dp[MAXN][MAXK], hasup[MAXN], minlcup[MAXN], hasdown[MAXN], minlcdown[MAXN];
int tintree[MAXN], altura[MAXN] ,Tt;
int marctree[MAXN];
void dfstree(int x, int p){
	marctree[x] = 1;
	tintree[x] = ++Tt;
	minlcup[x] = minlcdown[x] = 1e9 + 7;
	dp[x][0] = p;
	for(int k = 1; k < MAXK; k++){
		dp[x][k] = dp[dp[x][k-1]][k-1];
	}
	for(int i = 0; i < tree[x].size(); i++){
		int viz = tree[x][i].first;
		if(viz == p) continue;
		altura[viz] = altura[x] + 1;
		dfstree(viz, x);
	}
}

void dfsprecalc(int x, int p){
	marctree[x] = 2;
	
	for(int i = 0; i < tree[x].size(); i++){
		int viz = tree[x][i].first;
		if(viz == p) continue;
		dfsprecalc(viz, x);
		hasdown[x] |= hasdown[viz];
		hasup[x] |= hasup[viz];
		if(hasup[viz]) minlcup[x] = min(minlcup[x], minlcup[viz]);
		if(hasdown[viz]) minlcdown[x] = min(minlcdown[x], minlcdown[viz]);
	}
}

void dfscalc(int x, int p){
	marctree[x] = 3;
	for(int i = 0; i < tree[x].size(); i++){
		int viz = tree[x][i].first;
		int id = tree[x][i].second;
		if(viz == p) continue;
		dfscalc(viz, x);
		//printf("AQU: %d %d %d\n", viz, minlcdown[viz], minlcup[viz]);
		if(hasup[viz] && minlcup[viz] <= tin[x]){
			edges[id].maketype(viz, x,1);
		}
		else if(hasdown[viz] && minlcdown[viz] <= tin[x]){
			edges[id].maketype(x, viz,1);
		}else{edges[id].maketype(0,0,1);}
	}
}

int lca(int u, int v){
	if(altura[u] < altura[v]) swap(u,v);
	int dist = altura[u] - altura[v];
	for(int k = 0; k < MAXK; k++){
		if(dist & (1<<k)) u = dp[u][k];
	}
	if(u == v) return u;
	for(int k = MAXK - 1; k >= 0; k--){
		if(dp[u][k] == dp[v][k]) continue;
		u = dp[u][k];
		v = dp[v][k];
	}
	return dp[u][0];
}
int n, m, p;
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		edges[i].u = u;
		edges[i].v = v;
		grafo[u].push_back(make_pair(v, i));
		grafo[v].push_back(make_pair(u, i));
	}
	for(int i = 1; i <= n; i++){
		if(!marc[i]) dfsini(i, 0);
	}
	for(int i = 1; i <= m; i++){
		if(edges[i].tipo == 3){
			grafosemponte[edges[i].u].push_back(make_pair(edges[i].v, 0));
			grafosemponte[edges[i].v].push_back(make_pair(edges[i].u, 0));
		}
	}
	for(int i = 1; i <= n; i++){
		if(!comp[i])cmp++, dfssec(i);
	}
	for(int i = 0; i < bridge.size(); i++){
		int u = edges[bridge[i]].u;
		int v = edges[bridge[i]].v;
		tree[comp[u]].push_back(make_pair(comp[v], bridge[i]));
		tree[comp[v]].push_back(make_pair(comp[u], bridge[i]));
	}
	for(int i = 1; i <= cmp; i++){
		if(!marctree[i]) Tt = 0, dfstree(i, 0);
	}
	scanf("%d", &p);
	//memset(min)
	for(int i = 0; i < p; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		if(comp[u] == comp[v]) continue;
		u = comp[u];
		v = comp[v];
		int lc = lca(u,v);
	//	printf("LC: %d %d %d\n",u, v, lc );
		if(lc == u){
			hasdown[v] = 1;
			minlcdown[v] = min(minlcdown[v], tintree[u]);
		}else if(lc == v){
			hasup[u] = 1;
			minlcup[u] = min(minlcup[u], tintree[v]);

		}else{
			hasdown[v] = 1;
			minlcdown[v] = min(minlcdown[v], tintree[lc]);
			hasup[u] = 1;
			minlcup[u] = min(minlcup[u], tintree[lc]);
		}
	}
	for(int i = 1; i <= cmp; i++){
		if(marctree[i] != 2) dfsprecalc(i, 0);
	}
	for(int i = 1; i <= cmp; i++){
		if(marctree[i] != 3) dfscalc(i, 0);
	}
	for(int i = 1; i <= m; i++){
		if(edges[i].tipo == 3 || edges[i].tipo == 0) printf("B");
		if(edges[i].tipo == 2) printf("L");
		if(edges[i].tipo == 1) printf("R");
	}
	printf("\n");

}

Compilation message (stderr)

oneway.cpp: In function 'void dfsini(int, int)':
oneway.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < grafo[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfssec(int)':
oneway.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < grafosemponte[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfstree(int, int)':
oneway.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0; i < tree[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfsprecalc(int, int)':
oneway.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 0; i < tree[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfscalc(int, int)':
oneway.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 0; i < tree[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for(int i = 0; i < bridge.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
oneway.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |  scanf("%d", &p);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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