제출 #873739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873739		mdobric	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	8692 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

int n, m, p;
int a[100005], b[100005], poc[100005], kraj[100005];
vector <pair <int, int> > v[100005];
vector <pair <int, int> > e[100005];
int dt[100005], ft[100005], lw[100005];
int most[100005], blok[100005], d[100005];
int brojac = 1;
int br1 = 1, br2 = 1;
int parent[100005];
int rez[100005], ans[100005], max_lca[100005];
int go[100005][17];

bool isbroj(char x) {
	return x >= '0' && x <= '9';
}

long long unos() {
	long long res = 0;
	char ch;
	while (!isbroj(ch = getchar()));
	res = ch - '0';
	while (isbroj(ch = getchar())) {
		res = res * 10 + ch - '0';
	}
	return res;
}

int find (int x){
	if (parent[x] == x){
		return x;
	}
	return parent[x] = find(parent[x]);
}

void unite (int x, int y){
	int px = find(parent[x]);
	int py = find(parent[y]);
	if (px == py){
		return;
	}
	if (d[max_lca[px]] < d[max_lca[py]]){
		parent[py] = px;
	}
	else{
		parent[px] = py;
	}
	/*
	if (mp[x].size() > mp[y].size()){
		swap(px, py);
	}
	*/
	/*
	for (auto i : mp[px]){
		if (mp[py][i.first] == 1){
			mp[py].erase(i.first);
		}
		else{
			mp[py][i.first] = 1;
		}	
	}
	mp[px].clear();
	
	/*
	while (mp[px].size() > 0){
		//mp[px].begin();
		it = mp[px].begin();
		mp[py][it -> first]++;
		if (mp[py][it -> first] == 2){
			mp[py].erase(it -> first);
		}
		mp[px].erase(mp[px].begin());
	}
	*/
	//parent[px] = py;
	return;
}

void dfs (int x, int p, int cesta){
	//cout << " aaa " << x << " " << p << endl;
	blok[x] = brojac;
	lw[x] = dt[x];
	for (int i = 0; i < v[x].size(); i++){
		int x_novi = v[x][i].first;
		int in = v[x][i].second;
		if (dt[x_novi] == 0 and cesta != in and x != x_novi){
			e[x].push_back(make_pair(x_novi, in));
			dt[x_novi] = br1;
			parent[x_novi] = x_novi;
			br1++;
			d[x_novi] = d[x] + 1;
			dfs(x_novi, x, in);
			lw[x] = min(lw[x], lw[x_novi]);
		}
		else
		if (cesta != in and x != x_novi){
			lw[x] = min(lw[x], dt[x_novi]);
		}
	}
	if (cesta != -1 and lw[x] == dt[x]){
		most[cesta] = 1;
	}
	ft[x] = br2;
	br2++;
	return;
}

void dfs2 (int x, int cesta){
	for (int i = 0; i < e[x].size(); i++){
		int x_novi = e[x][i].first;
		int in = e[x][i].second;
		dfs2(x_novi, in);
		unite(x, x_novi);
	}
	int px = find(x);
	if (cesta != -1){
		rez[cesta] = ans[px];
	}
	return;
}

int idi (int x, int i){
	//cout << x << " " << i << endl;
	if (go[x][i] != -1){
		return go[x][i];
	}
	if (i == 0){
		go[x][i] = parent[x];
		return go[x][i];
	}
	int pola = idi(x, i - 1);
	go[x][i] = idi(pola, i - 1);
	return go[x][i];
}

int lca (int x, int y){
	if (blok[x] != blok[y]){
		return 0;
	}
	if (d[x] < d[y]){
		swap(x, y);
	}
	for (int i = 16; i >= 0; i--){
		int novi_x = idi(x, i);
		if (d[novi_x] >= d[y]){
			x = novi_x;
		}
	}
	if (x == y){
		return x;
	}
	for (int i = 16; i >= 0; i--){
		int novi_x = idi(x, i);
		int novi_y = idi(y, i);
		if (novi_x != novi_y){
			x = novi_x;
			y = novi_y;
		}
	}
	return parent[x];
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	n = unos();
	m = unos();
	for (int i = 1; i <= m; i++){
		a[i] = unos();
		b[i] = unos();
		v[a[i]].push_back(make_pair(b[i], i));
		v[b[i]].push_back(make_pair(a[i], i));
	}
	for (int i = 1; i <= n; i++){
		if (blok[i] == 0){
			d[i] = 1;
			blok[i] = brojac;
			br1 = 1, br2 = 1;
			dt[i] = 1;
			br1++;
			parent[i] = i;
			dfs(i, 0, -1);
			brojac++;
		}
	}
	/*
	for (int i = 1; i <= n; i++){
		cout << blok[i] << endl;
		cout << i << " : ";
		for (int j = 0; j < e[i].size(); j++){
			cout << e[i][j].first << " ";
		}
		cout << endl;
	}
	*/
	p = unos();
	for (int i = 1; i <= p; i++){
		poc[i] = unos();
		kraj[i] = unos();
		int lca_tr = lca(poc[i], kraj[i]);
		if (poc[i] != kraj[i]){
			if (max_lca[poc[i]] == 0 or d[lca_tr] < d[max_lca[poc[i]]]){
				max_lca[poc[i]] = lca_tr;
				ans[poc[i]] = i;
			}
			if (max_lca[kraj[i]] == 0 or d[lca_tr] < d[max_lca[kraj[i]]]){
				max_lca[kraj[i]] = lca_tr;
				ans[kraj[i]] = i;
			}
		}
		
	}
	brojac = 1;
	for (int i = 1; i <= n; i++){
		if (blok[i] == brojac){
			dfs2(i, -1);
			brojac++;
		}
	}
	//cout << "aaa" << endl;
	//dfs2(1, -1);
	for (int i = 1; i <= m; i++){
		if (rez[i] == 0 or most[i] == 0){
			cout << "B";
		}
		else{
			int k = kraj[rez[i]];
			int p = poc[rez[i]];
			//cout << a[i] << " " << b[i] << " " << p << " " << k << endl;
			if ((dt[a[i]] < dt[b[i]] and dt[b[i]] <= dt[k] and ft[b[i]] >= ft[k]) or (dt[a[i]] > dt[b[i]] and dt[a[i]] <= dt[p] and ft[a[i]] >= ft[p])){
				cout << "R";
			}
			else{
				cout << "L";
			}
		}
	}
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp:66:2: warning: "/*" within comment [-Wcomment]
   66 |  /*
      |   
oneway.cpp: In function 'void dfs(int, int, int)':
oneway.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (int i = 0; i < e[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~

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