oj.uz

Submission #499351

# Submission time Handle Problem Language Result Execution time Memory
499351 2021-12-28T04:37:18 Z kaxzert One-Way Streets (CEOI17_oneway) C++17
100 / 100
 112 ms 16436 KB 
/**
      00  00      11      00  00  111111  00000  111111  000000
      00 00      1111      0000      11   00     11  11  000000
      0000      11  11      00      11    00000  111111    00
      00 00    11111111    0000    11     00     11 11     00
      00  00  11      11  00  00  111111  00000  11  11    00
**/

#include<bits/stdc++.h>

using namespace std;

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define pi(a, b) pair<a, b>
#define fast ios::sync_with_stdio(false); cin.tie(0)

void setIO(string s) {
    if (sz(s) != 0) {
        freopen((s+".inp").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

void setIOusaco(string s) {
    if (sz(s) != 0) {
        freopen((s+".in").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}

void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}

#ifdef TAP
#define bug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define bug(x...) 
#endif

const int maxN = 200008;
int p[maxN], low[maxN], num[maxN], cnt, type[maxN], depth[maxN], out[maxN], in[maxN];
vt<int> ke[maxN];

int findset(int i) {
	return (p[i] == i ? i : p[i] = findset(p[i]));
}

void unionset(int con, int cha) {
	p[findset(con)] = findset(cha);
}

void dfs(int u, int p = 0) {
	num[u] = low[u] = ++cnt;
	int path = 0;
	trav(v, ke[u]) {
		if (v == p && path == 0) {
			++path;
			continue;
		}
		if (num[v] == 0) {
			dfs(v, u);
			if (ckmin(low[u], low[v])) unionset(u, v);
		} else {
			if (ckmin(low[u], num[v])) unionset(u, v);
		}
	}
}

void dfs2(int u) {
	num[u] = 1;
	type[u] += out[u];
	type[u] -= in[u];
	trav(v, ke[u]) {
		if (num[v] != 0) continue;
		depth[v] = depth[u]+(findset(u) != findset(v));
		dfs2(v);
		type[u] += type[v];
	}
}

int main() {
    #ifndef TAP 
    setIO("");
    //setIOusaco("CEOI17_oneway");
    #endif

    fast;
    int n, m;
    cin >> n >> m;
    vt<pi(int, int)> canh;
    fto(i, 1, m) {
    	int u, v;
    	cin >> u >> v;
    	ke[u].pb(v);
    	ke[v].pb(u);
    	canh.pb({u, v});
    }
    iota(p+1, p+n+1, 1);

    fto(i, 1, n) {
    	if (num[i] == 0) {
    		dfs(i);
    		num[i] = 0;
    	}
    }

    int q;
    cin >> q;
    fto(i, 1, q) {
    	int u, v;
    	cin >> u >> v;
    	out[u]++;
    	in[v]++;
    }

    fto(i, 1, n) num[i] = 0;

    fto(i, 1, n) {
    	if (num[i] == 0) dfs2(i);
    }

    trav(u, canh) {
    	if (findset(u.ff) == findset(u.ss)) {
    		cout << 'B';
    		continue;
    	}
    	int haveswap = 0;
    	if (depth[u.ff] < depth[u.ss]) {
    		haveswap = 1;
    		swap(u.ff, u.ss);
    	}
    	if (type[u.ff] == 0) cout << 'B';
    	if (type[u.ff] > 0) cout << (haveswap ? 'L' : 'R');
    	if (type[u.ff] < 0) cout << (haveswap ? 'R' : 'L');
    }
    cout << '\n';

    return 0;
}

Compilation message

oneway.cpp: In function 'void setIO(std::string)':
oneway.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen((s+".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void setIOusaco(std::string)':
oneway.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 47 ms 9128 KB Output is correct
12 Correct 39 ms 10300 KB Output is correct
13 Correct 51 ms 11644 KB Output is correct
14 Correct 57 ms 12740 KB Output is correct
15 Correct 66 ms 12896 KB Output is correct
16 Correct 56 ms 11088 KB Output is correct
17 Correct 58 ms 13136 KB Output is correct
18 Correct 58 ms 11608 KB Output is correct
19 Correct 48 ms 14268 KB Output is correct
20 Correct 43 ms 10408 KB Output is correct
21 Correct 40 ms 10176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5120 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 47 ms 9128 KB Output is correct
12 Correct 39 ms 10300 KB Output is correct
13 Correct 51 ms 11644 KB Output is correct
14 Correct 57 ms 12740 KB Output is correct
15 Correct 66 ms 12896 KB Output is correct
16 Correct 56 ms 11088 KB Output is correct
17 Correct 58 ms 13136 KB Output is correct
18 Correct 58 ms 11608 KB Output is correct
19 Correct 48 ms 14268 KB Output is correct
20 Correct 43 ms 10408 KB Output is correct
21 Correct 40 ms 10176 KB Output is correct
22 Correct 76 ms 13400 KB Output is correct
23 Correct 112 ms 11796 KB Output is correct
24 Correct 72 ms 11796 KB Output is correct
25 Correct 62 ms 16436 KB Output is correct
26 Correct 63 ms 12996 KB Output is correct
27 Correct 90 ms 11880 KB Output is correct
28 Correct 32 ms 6980 KB Output is correct
29 Correct 60 ms 10040 KB Output is correct
30 Correct 54 ms 10168 KB Output is correct
31 Correct 55 ms 10440 KB Output is correct
32 Correct 55 ms 12728 KB Output is correct