oj.uz

Submission #535444

# Submission time Handle Problem Language Result Execution time Memory
535444 2022-03-10T09:25:24 Z Asymmetry One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3 ms 5076 KB 
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 101000;
int n, m, q, a, b, l;
int dp[N];
int kr[N][2];
int sss[N];
int odw[N];
int gle[N];
int par[N];
int odp[N];
int stp[N];
int pd[N];
vector<int> v[N];
vector<pair<int, int>> vv[N];

void dfs_gle(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			gle[i] = gle[x] + 1;
			par[i] = x;
			dfs_gle(i);
		}
	}
}

void dfs_dp(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			dfs_dp(i);
			dp[x] += dp[i];
		}
	}
}

void dfs_sss(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			if (dp[i] > 1) {
				sss[i] = sss[x];
			}
			dfs_sss(i);
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
		kr[i][0] = a;
		kr[i][1] = b;
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_gle(i);
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (gle[kr[i][0]] > gle[kr[i][1]]) {
			odp[i] = 1;
			swap(kr[i][0], kr[i][1]);
		}
		++dp[kr[i][1]];
		--dp[kr[i][0]];
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_dp(i);
		}
		sss[i] = i;
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_sss(i);
		}
	}
	//~ for (int i = 1; i <= n; ++i) {
		//~ printf("%d ", sss[i]);
	//~ }
	//~ printf("\n");
	for (int i = 1; i <= m; ++i) {
		if (sss[kr[i][0]] == sss[kr[i][1]]) {
			odp[i] = 2;
		}
		else {
			vv[sss[kr[i][0]]].push_back({sss[kr[i][1]], i});
			vv[sss[kr[i][1]]].push_back({sss[kr[i][0]], i});
			++stp[sss[kr[i][0]]];
			++stp[sss[kr[i][1]]];
		}
	}
	scanf("%d", &q);
	for (int i = 1; i <= q; ++i) {
		scanf("%d%d", &a, &b);
		++pd[sss[a]];
		--pd[sss[b]];
	}
	queue<int> que;
	for (int i = 1; i <= n; ++i) {
		if (stp[i] == 1) {
			que.push(i);
		}
	}
	++l;
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		odw[x] = l;
		for (auto i : vv[x]) {
			if (odw[i.first] < l) {
				--stp[i.first];
				if ((pd[x] > 0) == (x == kr[i.second][1])) {
					odp[i.second] ^= 1;
				}
				else if (pd[x] == 0) {
					odp[i.second] = 2;
				}
				pd[i.first] += pd[x];
				if (stp[i.first] == 1) {
					que.push(i.first);
				}
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (odp[i] == 0) {
			printf("R");
		}
		else if (odp[i] == 1) {
			printf("L");
		}
		else {
			printf("B");
		}
	}
	return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5060 KB Output is correct
3 Incorrect 3 ms 5076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5060 KB Output is correct
3 Incorrect 3 ms 5076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5060 KB Output is correct
3 Incorrect 3 ms 5076 KB Output isn't correct
4 Halted 0 ms 0 KB -