Submission #211095

#	Time	Username	Problem	Language	Result	Execution time	Memory
211095		mhy908	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	8 ms	2816 KiB

oneway

#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 (stderr)

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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40