oj.uz

Submission #211095

# Submission time Handle Problem Language Result Execution time Memory
211095 2020-03-19T08:18:30 Z mhy908 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 8 ms 2816 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

char ans[100010];

const LL hashnum=1000000ll;
unordered_map<LL, int> ump;
void inedge(int a, int b, int i){
    ump[hashnum*a+b]=i;
    ump[hashnum*b+a]=-i;
}
void getedge(int a, int b, char c){
    int temp=ump[hashnum*a+b];
    if(temp<0){
        if(c=='L')c='R';
        else c='L';
        temp*=-1;
    }
    ans[temp]=c;
}


int n, m, p;
vector<int> link[100010];
int arr[100010], dfsnum[100010], re;

int solve(int num, int par){
    dfsnum[num]=++re;
    int ret=re;
    for(int i:link[num]){
        if(i==par)continue;
        if(!dfsnum[i]){
            int temp=solve(i, num);
            if(temp>dfsnum[num]){
                if(arr[i]<0)getedge(num, i, 'R');
                if(arr[i]>0)getedge(num, i, 'L');
            }
            ret=min(ret, temp);
            arr[num]+=arr[i];
        }
        else ret=min(ret, dfsnum[i]);
    }
    return ret;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int a, b;
        ans[i]='B';
        scanf("%d %d", &a, &b);
        inedge(a, b, i);
        link[a].pb(b);
        link[b].pb(a);
    }
    scanf("%d", &p);
    for(int i=1; i<=p; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a]++, arr[b]--;
    }
    for(int i=1; i<=n; i++){
        if(dfsnum[i])continue;
        solve(i, 0);
    }
    for(int i=1; i<=m; i++)printf("%c", ans[i]);
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Incorrect 8 ms 2816 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Incorrect 8 ms 2816 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Incorrect 8 ms 2816 KB Output isn't correct
10 Halted 0 ms 0 KB -