oj.uz

Submission #167387

# Submission time Handle Problem Language Result Execution time Memory
167387 2019-12-07T22:30:03 Z 2fat2code One-Way Streets (CEOI17_oneway) C++14
100 / 100
 130 ms 17728 KB 
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mod=1e9+7;
const int modp=1999999973;
const int modx=998244353;

int n,m,k,height[100005],comp[100005],grad[100005],val[100005];
char ans[100005];
vector<pair<int,int>>edge,nod[100005];
vector<int>nod2[100005],bridge;

int DFS1(int node,int par,int cnt){
    height[node]=height[par]+1;
    int res=height[node];
    for(auto it:nod[node]){
        if(it.second!=cnt){
            int x=it.first;
            int y=it.second;
            if(height[x]){
                res=min(res,height[x]);
                ans[y]='B';
            }
            else res=min(res,DFS1(x,node,y));
        }
    }
    if(res<height[node]){
        ans[cnt]='B';
        nod2[par].push_back(node);
        nod2[node].push_back(par);
    }
    else if(cnt>=1) bridge.push_back(cnt);
    return res;
}

void DFS2(int node,int curr){
    comp[node]=curr;
    for(auto i:nod2[node]) if(comp[i]==0) DFS2(i,curr);
}

int DFS3(int node,int par,int cnt){
    height[node]=height[par]+1;
    for(auto it:nod[node]){
        if(it.first!=par){
            grad[node]+=DFS3(it.first,node,it.second);
        }
    }
    if(grad[node]==0) ans[cnt]='B';
    else if(grad[node]<0 ^ edge[cnt-1].fr==par) ans[cnt]='L';
    else ans[cnt]='R';
    return grad[node];
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
  //  ifstream cin("input.in");
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin >> x >> y;
        edge.push_back({x,y});
        nod[x].push_back({y,i});
        nod[y].push_back({x,i});
    }
    for(int i=1;i<=n;i++) if(!height[i]) DFS1(i,i,0);
    for(int i=1;i<=n;i++) if(comp[i]==0) DFS2(i,i);
    for(int i=1;i<=n;i++) nod[i].clear();
    for(auto i:bridge){
        edge[i-1].fr=comp[edge[i-1].fr];
        edge[i-1].sc=comp[edge[i-1].sc];
        int x=edge[i-1].fr;
        int y=edge[i-1].sc;
        nod[x].push_back({y,i});
        nod[y].push_back({x,i});
    }
    cin >> k;
    for(int i=1;i<=k;i++){
        int x,y;
        cin >> x >> y;
        x=comp[x];
        y=comp[y];
        grad[x]++;
        grad[y]--;
    }
    for(int i=1;i<=n;i++) height[i]=0;
    for(int i=1;i<=n;i++) if(height[i]==0) DFS3(i,i,0);
    for(int i=1;i<=m;i++) cout << ans[i] ;
    cout << '\n';
    return 0;
}

Compilation message

oneway.cpp: In function 'int DFS3(int, int, int)':
oneway.cpp:66:23: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
     else if(grad[node]<0 ^ edge[cnt-1].fr==par) ans[cnt]='L';
             ~~~~~~~~~~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5116 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5116 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct
11 Correct 58 ms 10988 KB Output is correct
12 Correct 69 ms 12140 KB Output is correct
13 Correct 87 ms 13584 KB Output is correct
14 Correct 103 ms 14852 KB Output is correct
15 Correct 107 ms 14956 KB Output is correct
16 Correct 95 ms 13032 KB Output is correct
17 Correct 77 ms 14184 KB Output is correct
18 Correct 83 ms 13156 KB Output is correct
19 Correct 77 ms 15220 KB Output is correct
20 Correct 75 ms 12652 KB Output is correct
21 Correct 72 ms 12648 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5116 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct
11 Correct 58 ms 10988 KB Output is correct
12 Correct 69 ms 12140 KB Output is correct
13 Correct 87 ms 13584 KB Output is correct
14 Correct 103 ms 14852 KB Output is correct
15 Correct 107 ms 14956 KB Output is correct
16 Correct 95 ms 13032 KB Output is correct
17 Correct 77 ms 14184 KB Output is correct
18 Correct 83 ms 13156 KB Output is correct
19 Correct 77 ms 15220 KB Output is correct
20 Correct 75 ms 12652 KB Output is correct
21 Correct 72 ms 12648 KB Output is correct
22 Correct 124 ms 15356 KB Output is correct
23 Correct 123 ms 14232 KB Output is correct
24 Correct 130 ms 14164 KB Output is correct
25 Correct 115 ms 17728 KB Output is correct
26 Correct 125 ms 15096 KB Output is correct
27 Correct 120 ms 14184 KB Output is correct
28 Correct 53 ms 9320 KB Output is correct
29 Correct 99 ms 13548 KB Output is correct
30 Correct 98 ms 13672 KB Output is correct
31 Correct 97 ms 13820 KB Output is correct
32 Correct 107 ms 15476 KB Output is correct