oj.uz

Submission #211077

# Submission time Handle Problem Language Result Execution time Memory
211077 2020-03-19T07:44:32 Z mhy908 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 8 ms 5632 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL hashnum=1000000ll;

const int MAXN=100000;
struct UNION_FIND{
    int par[MAXN+10];
    UNION_FIND(){for(int i=1; i<=MAXN; i++)par[i]=i;}
    int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
    void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}uf;

int n, m, p;
vector<int> link[100010];
vector<pair<int, pii> > tlink[100010];
int arr[100010];
vector<pii> bridge;
int dfsnum[100010], re;
bool ch[100010];
char ans[100010];
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 dfs(int num, int par){
    dfsnum[num]=++re;
    int ret=re;
    for(auto i:link[num]){
        if(i==par)continue;
        if(!dfsnum[i]){
            int temp=dfs(i, num);
            if(temp>dfsnum[num])bridge.pb(mp(min(num, i), max(num, i)));
            else{
                inedge(num, i, 'B');
                uf.mergepar(num, i);
            }
            ret=min(ret, temp);
        }
        else ret=min(ret, dfsnum[i]);
    }
    return ret;
}
void solve(int num, int par, pii t){
    ch[num]=true;
    for(auto i:tlink[num]){
        if(i.F==par)continue;
        solve(i.F, num, i.S);
        arr[num]+=arr[i.F];
    }
    if(arr[num]<0)getedge(t.F, t.S, 'R');
    if(arr[num]>0)getedge(t.F, t.S, 'L');
}
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);
        if(a!=b){
            link[a].pb(b);
            link[b].pb(a);
        }
    }
    for(int i=1; i<=n; i++){
        if(dfsnum[i])continue;
        dfs(i, 0);
    }
    for(auto i:bridge){
        int a=uf.findpar(i.F), b=uf.findpar(i.S);
        tlink[a].pb(mp(b, i));
        tlink[b].pb(mp(a, mp(i.S, i.F)));
    }
    scanf("%d", &p);
    for(int i=1; i<=p; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        a=uf.findpar(a);
        b=uf.findpar(b);
        arr[a]++, arr[b]--;
    }
    for(int i=1; i<=n; i++){
        if(ch[i])continue;
        solve(i, 0, mp(0, 0));
    }
    for(int i=1; i<=m; i++)printf("%c", ans[i]);
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:76: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:80: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:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:99: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 8 ms 5504 KB Output is correct
2 Correct 7 ms 5376 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 8 ms 5632 KB Output is correct
7 Correct 8 ms 5632 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Incorrect 8 ms 5504 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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