oj.uz

Submission #419019

# Submission time Handle Problem Language Result Execution time Memory
419019 2021-06-06T10:41:43 Z RambaXGorilla One-Way Streets (CEOI17_oneway) C++11
100 / 100
 424 ms 39268 KB 
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<utility>
using namespace std;
int N, M, P;
pair <int,int> roads[100010];
pair <int,int> save[100010];
int imps[100010][3];
int dfsCnt = 0;
bool vis[100010];
int dfsNums[100010];
int dfsLows[100010];
int dfsPars[100010];
int cons[100010];
int treePars[100010];
int dirs[100010];
char trans[] = {'L', 'B', 'R'};
vector <int> adjGraph[100010];
vector <int> adjTree[100010];
vector <int> adjCycles[100010];
map < pair <int,int>, int> goBack;
map < pair <int,int>, bool> bridges;
void getBridges(int u){
    dfsNums[u] = dfsLows[u] = dfsCnt++;
    for(int i = 0;i < adjGraph[u].size();i++){
        int v = adjGraph[u][i];
        if(dfsNums[v] == -1){
            dfsPars[v] = u;
            getBridges(v);
            if(dfsLows[v] > dfsNums[u]){
                bridges[make_pair(min(u, v), max(u, v))] = true;
            }
            dfsLows[u] = min(dfsLows[u], dfsLows[v]);
        }
        else if(dfsPars[u] != v || goBack[make_pair(min(u, v), max(u, v))] > 1){
            dfsLows[u] = min(dfsLows[u], dfsNums[v]);
        }      
    }
}
void getCycles(int u, int r){
    cons[u] = r;
    for(int i = 0;i < adjCycles[u].size();i++){
        int v = adjCycles[u][i];
        if(cons[v] == -1){
            getCycles(v, r);
        }
    }
}
void getTreePars(int u){
    for(int i = 0;i < adjTree[u].size();i++){
        int v = adjTree[u][i];
        if(treePars[v] == -1){
            treePars[v] = u;
            getTreePars(v);
        }
    }
}
void addTreeDirs(int u){
    vis[u] = true;
    for(int i = 0;i < adjTree[u].size();i++){
        int v = adjTree[u][i];
        if(!vis[v]){
            addTreeDirs(v);
            dirs[u] += dirs[v];
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 0;i < M;i++){
        scanf("%d%d",&roads[i].first,&roads[i].second);
        save[i] = roads[i];
        if(roads[i].first > roads[i].second){
            swap(roads[i].first, roads[i].second);
        }
        else if(roads[i].first == roads[i].second){
            continue;
        }
        goBack[roads[i]] += 1;
        if(goBack[roads[i]] == 1){
            adjGraph[roads[i].first].push_back(roads[i].second);
            adjGraph[roads[i].second].push_back(roads[i].first);
        }
    }
    scanf("%d",&P);
    for(int i = 0;i < P;i++){
        scanf("%d%d",&imps[i][0],&imps[i][1]);
    }
    for(int i = 0;i < 100010;i++){
        dfsNums[i] = -1;
        cons[i] = -1;
        treePars[i] = -1;
        dirs[i] = 0;
        vis[i] = false;
    }
    for(int i = 1;i < N + 1;i++){
        if(dfsNums[i] == -1){
            getBridges(i);
        }
    }
    for(int i = 0;i < M;i++){
        if(!bridges[roads[i]]){
            adjCycles[roads[i].first].push_back(roads[i].second);
            adjCycles[roads[i].second].push_back(roads[i].first);
        }
    }
    int cnt = 0;
    for(int i = 1;i < N + 1;i++){
        if(cons[i] == -1){
            cnt += 1;
            getCycles(i, cnt);
        }
    }
    for(int i = 0;i < M;i++){
        if(bridges[roads[i]]){
            adjTree[cons[roads[i].first]].push_back(cons[roads[i].second]);
            adjTree[cons[roads[i].second]].push_back(cons[roads[i].first]);
        }
    }
    for(int i = 1;i < cnt + 1;i++){
        if(treePars[i] == -1){
            treePars[i] = 0;
            getTreePars(i);
        }
    }
    for(int i = 0;i < P;i++){
        dirs[cons[imps[i][0]]] += 1;
        dirs[cons[imps[i][1]]] += -1;
    }
    for(int i = 1;i < cnt + 1;i++){
        if(!vis[i]){
            addTreeDirs(i);
        }
    }
    for(int i = 0;i < M;i++){
        int u = save[i].first;
        int v = save[i].second;
        int uT = cons[u];
        int vT = cons[v];
        if(uT == vT){
            printf("B");
            continue;
        }
        int d;
        if(treePars[uT] == vT){
            d = dirs[uT];
        }
        else{
            d = dirs[vT] * -1;
        }
        if(d != 0){
            d /= abs(d);
        }
        printf("%c",trans[d + 1]);
    }
}

Compilation message

oneway.cpp: In function 'void getBridges(int)':
oneway.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0;i < adjGraph[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void getCycles(int, int)':
oneway.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0;i < adjCycles[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void getTreePars(int)':
oneway.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0;i < adjTree[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void addTreeDirs(int)':
oneway.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0;i < adjTree[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d%d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~
oneway.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d%d",&roads[i].first,&roads[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%d",&P);
      |     ~~~~~^~~~~~~~~
oneway.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         scanf("%d%d",&imps[i][0],&imps[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 5 ms 8992 KB Output is correct
3 Correct 7 ms 9164 KB Output is correct
4 Correct 7 ms 9128 KB Output is correct
5 Correct 7 ms 9256 KB Output is correct
6 Correct 6 ms 9164 KB Output is correct
7 Correct 9 ms 9164 KB Output is correct
8 Correct 8 ms 9132 KB Output is correct
9 Correct 7 ms 9164 KB Output is correct
10 Correct 6 ms 9164 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 5 ms 8992 KB Output is correct
3 Correct 7 ms 9164 KB Output is correct
4 Correct 7 ms 9128 KB Output is correct
5 Correct 7 ms 9256 KB Output is correct
6 Correct 6 ms 9164 KB Output is correct
7 Correct 9 ms 9164 KB Output is correct
8 Correct 8 ms 9132 KB Output is correct
9 Correct 7 ms 9164 KB Output is correct
10 Correct 6 ms 9164 KB Output is correct
11 Correct 236 ms 29008 KB Output is correct
12 Correct 285 ms 30088 KB Output is correct
13 Correct 316 ms 31356 KB Output is correct
14 Correct 424 ms 32620 KB Output is correct
15 Correct 329 ms 32904 KB Output is correct
16 Correct 413 ms 31552 KB Output is correct
17 Correct 338 ms 33436 KB Output is correct
18 Correct 369 ms 31536 KB Output is correct
19 Correct 344 ms 34740 KB Output is correct
20 Correct 244 ms 29984 KB Output is correct
21 Correct 219 ms 29048 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 5 ms 8992 KB Output is correct
3 Correct 7 ms 9164 KB Output is correct
4 Correct 7 ms 9128 KB Output is correct
5 Correct 7 ms 9256 KB Output is correct
6 Correct 6 ms 9164 KB Output is correct
7 Correct 9 ms 9164 KB Output is correct
8 Correct 8 ms 9132 KB Output is correct
9 Correct 7 ms 9164 KB Output is correct
10 Correct 6 ms 9164 KB Output is correct
11 Correct 236 ms 29008 KB Output is correct
12 Correct 285 ms 30088 KB Output is correct
13 Correct 316 ms 31356 KB Output is correct
14 Correct 424 ms 32620 KB Output is correct
15 Correct 329 ms 32904 KB Output is correct
16 Correct 413 ms 31552 KB Output is correct
17 Correct 338 ms 33436 KB Output is correct
18 Correct 369 ms 31536 KB Output is correct
19 Correct 344 ms 34740 KB Output is correct
20 Correct 244 ms 29984 KB Output is correct
21 Correct 219 ms 29048 KB Output is correct
22 Correct 335 ms 35752 KB Output is correct
23 Correct 368 ms 33912 KB Output is correct
24 Correct 398 ms 33908 KB Output is correct
25 Correct 400 ms 39268 KB Output is correct
26 Correct 331 ms 35260 KB Output is correct
27 Correct 380 ms 33900 KB Output is correct
28 Correct 104 ms 14648 KB Output is correct
29 Correct 263 ms 31852 KB Output is correct
30 Correct 259 ms 31940 KB Output is correct
31 Correct 339 ms 32316 KB Output is correct
32 Correct 222 ms 32180 KB Output is correct