oj.uz

Submission #394152

# Submission time Handle Problem Language Result Execution time Memory
394152 2021-04-25T22:24:05 Z Pichon5 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 19004 KB 
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
using namespace std;
const int MA=1e5+5;
vector<pair<int,int> > G[MA];
int vis[MA];
int arc[MA];
int num=0;
set<pair<int,int> >st;
int puente[MA];
string res;
void tarjan(int nodo, int ant){
    num++;
    vis[nodo]=arc[nodo]=num;
    for(int it =0;it<G[nodo].size();it++){
        int to=G[nodo][it].F,ind=G[nodo][it].S;
        if(ind==ant)continue;
        if(vis[to]==0){
            tarjan(to,ind);
            if(arc[to]>vis[nodo]){
                puente[ind]=1;
            }
            arc[nodo]=min(arc[nodo],arc[to]);
        }else{
            arc[nodo]=min(arc[nodo],vis[to]);
        }
    }
}
vector<pair<int,int> > G2[MA];
int C[MA];
int color=0;
void coloring(int nodo){
    C[nodo]=color;
    for(int i=0;i<G[nodo].size();i++){
        int to=G[nodo][i].F,ind=G[nodo][i].S;
        if(puente[ind] or C[to])continue;
        coloring(to);
    }
}
int B[MA];
void dfs(int nodo, int padre){
    for(int i=0;i<G2[nodo].size();i++){
        int to=G2[nodo][i].F,ind=G2[nodo][i].S;
        if(to==padre)continue;
        B[to]=ind;
        dfs(to,nodo);
    }
}
int main()
{
    int n,m,p,a,b;
    cin>>n>>m;
    vector<pair<int,int> >E;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        G[a].pb({b,i});G[b].pb({a,i});
        E.pb({a,b});
    }
    res.assign(m,'B');
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            tarjan(i,-1);
        }
    }
    for(int i=1;i<=n;i++){
        if(C[i])continue;
        color++;
        coloring(i);
    }

    for(int i=0;i<m;i++){
        if(puente[i]==0)continue;
        int A=C[E[i].F],B=C[E[i].S];
        G2[A].pb({B,i});
        G2[B].pb({A,i});
    }
    cin>>p;
    for(int i=0;i<p;i++){
        cin>>a>>b;
        a=C[a],b=C[b];
        if(a==b)continue;
        dfs(a,-1);
        int nodo=b;
        while(nodo!=a){
            int ind=B[nodo];
            int from=C[E[ind].F];
            if(from==nodo){
                from=C[E[ind].S];
                res[ind]='L';
            }else{
                res[ind]='R';
            }
            nodo=from;
        }
    }
    cout<<res<<endl;

    return 0;
}

Compilation message

oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int it =0;it<G[nodo].size();it++){
      |                   ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void coloring(int)':
oneway.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<G[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<G2[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 6 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 6 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 78 ms 11140 KB Output is correct
12 Correct 84 ms 12384 KB Output is correct
13 Correct 101 ms 13616 KB Output is correct
14 Correct 128 ms 14924 KB Output is correct
15 Correct 138 ms 15356 KB Output is correct
16 Correct 137 ms 16568 KB Output is correct
17 Correct 638 ms 17992 KB Output is correct
18 Correct 641 ms 16468 KB Output is correct
19 Correct 534 ms 19004 KB Output is correct
20 Correct 86 ms 11740 KB Output is correct
21 Correct 84 ms 11864 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 6 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 6 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 78 ms 11140 KB Output is correct
12 Correct 84 ms 12384 KB Output is correct
13 Correct 101 ms 13616 KB Output is correct
14 Correct 128 ms 14924 KB Output is correct
15 Correct 138 ms 15356 KB Output is correct
16 Correct 137 ms 16568 KB Output is correct
17 Correct 638 ms 17992 KB Output is correct
18 Correct 641 ms 16468 KB Output is correct
19 Correct 534 ms 19004 KB Output is correct
20 Correct 86 ms 11740 KB Output is correct
21 Correct 84 ms 11864 KB Output is correct
22 Execution timed out 3073 ms 18256 KB Time limit exceeded
23 Halted 0 ms 0 KB -