Submission #199518

#	Time	Username	Problem	Language	Result	Execution time	Memory
199518		Markomafko972	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	12 ms	10232 KiB

oneway

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int t, n, m, q, put1, put2;
pair<int, int> edg[100002];
int spoji[100002];
vector< pair<int, int> > v[100002];
vector< pair<int, int> > vnovi[100002];
vector< pair<int, int> > gore[100002];
int discovery[100002];
int min_gore[100002];
int trendisc = 0;
//vector< pair<int, int> > sol;

void dfs(int cvor, int prt) {
	trendisc ++;
	discovery[cvor] = trendisc;
	
	for (int i = 0; i < v[cvor].size(); i++) {
		int sus = v[cvor][i].X;
		if (sus != prt) {
			if (discovery[sus] == 0) {
				vnovi[cvor].push_back({sus, v[cvor][i].Y});
				dfs(sus, cvor);
			}
			else {
				gore[cvor].push_back({sus, v[cvor][i].Y});
			}
		}
	}
}

int set_gore(int cvor, int prt) {
	min_gore[cvor] = discovery[cvor];
	
	for (int i = 0; i < gore[cvor].size(); i++) {
		min_gore[cvor] = min(min_gore[cvor], discovery[ gore[cvor][i].X ]);
	}
	
	for (int i = 0; i < vnovi[cvor].size(); i++) {
		int sus = vnovi[cvor][i].X;
		if (sus != prt) {
			min_gore[cvor] = min(min_gore[cvor], set_gore(sus, cvor));
		}
	}
	
	for (int i = 0; i < vnovi[cvor].size(); i++) {
		int sus = vnovi[cvor][i].X;
		if (sus != prt && discovery[cvor] < min_gore[sus]) {
			spoji[ vnovi[cvor][i].Y ] = -1;
		}
	}
	
	return min_gore[cvor];
}

int rod[100002];
vector< pair<int, int> > graf[100002];

int find(int cvor) {
	if (cvor == rod[cvor]) return cvor;
	return rod[cvor] = find(rod[cvor]);
}


void unija(int cvor1, int cvor2) {
	cvor1 = find(cvor1);
	cvor2 = find(cvor2);
	if (cvor1 == cvor2) return;
	if (rand() % 2 == 0) {
		rod[cvor1] = cvor2;
	}
	else {
		rod[cvor2] = cvor1;
	}
}

string sol = "";

int dub[100002];
int lift[25][100002];

void postavi(int cvor, int prt) {
	for (int i = 0; i < graf[cvor].size(); i++) {
		int sus = graf[cvor][i].X;
		if (sus != prt) {
			lift[0][sus] = cvor;
			//cout << sus << " -> " << cvor << endl;
			dub[sus] = dub[cvor]+1;
			postavi(sus, cvor);
		}
	}
}

int prefg[100002];
int prefd[100002];

int findlca(int cvor1, int cvor2) {
	if (dub[cvor1] < dub[cvor2]) swap(cvor1, cvor2);
	for (int i = 19; i >= 0; i--) {
		if (dub[ lift[i][cvor1] ] >= dub[cvor2]) {
			cvor1 = lift[i][cvor1];
		}
	}
	
	if (cvor1 == cvor2) return cvor1;
	
	for (int i = 19; i >= 0; i--) {
		if (lift[i][cvor1] != lift[i][cvor2]) {
			cvor1 = lift[i][cvor1];
			cvor2 = lift[i][cvor2];
		}
	}
	
	return lift[0][cvor1];
}

void rek(int cvor, int prt) {
	for (int i = 0; i < graf[cvor].size(); i++) {
		int sus = graf[cvor][i].X;
		if (prt != sus) {
			rek(sus, cvor);
			
			if (prefg[sus] > 0) {
				sol[ graf[cvor][i].Y ] = 'X';
			}
			
			if (prefd[sus] > 0) {
				sol[ graf[cvor][i].Y ] = 'Y';
			}
			
			prefg[cvor] += prefg[sus];
			prefd[cvor] += prefd[sus];
		}
	}
}

int main () {
	
	srand(time(NULL));
	cin >> n >> m;
	memset(dub, -1, sizeof dub);
	for (int i = 1; i <= n; i++) {
		rod[i] = i;
	}
	
	for (int i = 0; i < m; i++) {
		sol.push_back('B');
		cin >> edg[i].X >> edg[i].Y;
		v[edg[i].X].push_back({edg[i].Y, i});
		v[edg[i].Y].push_back({edg[i].X, i});
	}
	
	dfs(1, 0);
	set_gore(1, 0);
	
	for (int i = 0; i < m; i++) {
		if (spoji[i] != -1) {
			unija(edg[i].X, edg[i].Y);
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			int tr1 = find(i);
			int tr2 = find(v[i][j].X);
			if (tr1 != tr2) {
				graf[tr1].push_back({tr2, v[i][j].Y});
				//graf[tr2].push_back({tr1, v[i][j].Y});
			}
		}
	}
	
	int glavni = 0;
	for (int i = 1; i <= n; i++) {
		if (graf[i].size() > 0) {
			glavni = i;
			break;
		}
	}
	postavi(glavni, 0);
	
	for (int i = 1; i < 20; i++) {
		for (int j = 1; j <= n; j++) {
			lift[i][j] = lift[i-1][ lift[i-1][j] ];
		}
	}
	
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> put1 >> put2;
		put1 = find(put1);
		put2 = find(put2);
		
		prefg[put1] ++;
		prefd[put2] ++;
		
		int lca = findlca(put1, put2);
		
		prefg[lca] --;
		prefd[lca] --;
	}
	
	rek(glavni, 0);
	
	/*for (int i = 1; i <= n; i++) {
		cout << i << ": " << prefg[i] << " " << prefd[i] << endl;
	}*/
	
	for (int i = 0; i < m; i++) {
		if (sol[i] != 'B') {
			if (dub[ edg[i].X ] < dub[ edg[i].Y ]) {
				if (sol[i] == 'X') sol[i] = 'L';
				else sol[i] = 'R';
			}
			else {
				if (sol[i] == 'X') sol[i] = 'R';
				else sol[i] = 'L';
			}
		}
	}
	
	cout << sol;
	
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[cvor].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'int set_gore(int, int)':
oneway.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < gore[cvor].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vnovi[cvor].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vnovi[cvor].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void postavi(int, int)':
oneway.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < graf[cvor].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void rek(int, int)':
oneway.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < graf[cvor].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:166:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v[i].size(); j++) {
                   ~~^~~~~~~~~~~~~

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