oj.uz

Submission #1061995

# Submission time Handle Problem Language Result Execution time Memory
1061995 2024-08-16T16:37:42 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 15004 KB 
#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<char, int> ci;
typedef pair<string, int> si;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define inf INT_MAX/2
#define fro front

vector<vector<ii>> x(100005);
int vis[100005];
int hi[100005];
int dp[100005];
int bridges[100005];
vector<ii> rpath;
vector<ii> paths;

void recans(int node){
    if(paths[node].first == -1){
        return;
    }else{
        rpath.pb(ii(paths[node].second, paths[node].first));
        recans(paths[node].first);
    }
    return;
}

int dfs(int n, int h, int idxeje){
    vis[n] = 1;
    hi[n] = h;
    dp[n] = h;
    for(auto e:x[n]){
        if(e.se == idxeje)continue;
        int nxt = e.fi;
        if(vis[nxt] == 2){
            continue;
        }
        if(vis[nxt] == 1){
            dp[n] = min(dp[nxt], dp[n]);
            continue;
        }
        int k = dfs(e.fi, h+1, e.se);
        dp[n] = min(k, dp[n]);
    }
    if(idxeje == -1){
        return dp[n];
    }
    if(dp[n] >= h){
        bridges[idxeje] = 1;
    }
    vis[n] = 2;
    return dp[n];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, p; cin >> n >> m;
    vector<ii> d(m);
    for(int i = 0; i < m; ++i){
        int y, z; cin >> y >> z;
        x[y].pb(ii(z, i));
        x[z].pb(ii(y, i));
        d[i] = ii(y, z);
    }
    for(int i = 1; i <= n; ++i){
        hi[i] = inf;
    }
    for(int i = 1; i <= n; ++i){
        if(vis[i] == 0){
            dfs(i, 0, -1);
            hi[i] = 0;
        }
    }
    char dir[m];
    for(int i = 0; i < m; ++i){
        dir[i] = 'B';
    }
    cin >> p;
    while(p--){
        int u, v; cin >> u >> v;
        int dist[n+1];
        for(int i = 1; i <= n; ++i){
            dist[i] = inf;
        }
        queue<int> q;
        q.push(u);
        dist[u] = 0;
        vector<ii> path(n+1, ii(-1, -1));
        while(!q.empty()){
            int no = q.fro();
            q.pop();
            for(auto e:x[no]){
                if(dist[e.fi] == inf){
                    path[e.fi] = ii(no, e.se);
                    q.push(e.fi);
                    dist[e.fi] = dist[no]+1;
                }else{
                    continue;
                }
            }
        }
        paths = path;
        recans(v);
        reverse(whole(rpath));
        for(int i = 0; i < rpath.size(); ++i){
            if(bridges[rpath[i].first]){
                if(rpath[i].se == d[rpath[i].fi].fi){
                    dir[rpath[i].first] = 'R';
                }else{
                    dir[rpath[i].first] = 'L';
                }
            }
        }
        //cout << endl << endl;
        rpath.clear();
        paths.clear();
    }
    for(auto e:dir){
        cout << e;
    }
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:117:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int i = 0; i < rpath.size(); ++i){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 108 ms 9060 KB Output is correct
12 Correct 148 ms 10672 KB Output is correct
13 Correct 204 ms 11984 KB Output is correct
14 Correct 269 ms 13212 KB Output is correct
15 Correct 256 ms 13460 KB Output is correct
16 Correct 36 ms 12112 KB Output is correct
17 Correct 371 ms 13504 KB Output is correct
18 Correct 266 ms 12160 KB Output is correct
19 Correct 324 ms 15004 KB Output is correct
20 Correct 203 ms 10244 KB Output is correct
21 Correct 199 ms 10292 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 108 ms 9060 KB Output is correct
12 Correct 148 ms 10672 KB Output is correct
13 Correct 204 ms 11984 KB Output is correct
14 Correct 269 ms 13212 KB Output is correct
15 Correct 256 ms 13460 KB Output is correct
16 Correct 36 ms 12112 KB Output is correct
17 Correct 371 ms 13504 KB Output is correct
18 Correct 266 ms 12160 KB Output is correct
19 Correct 324 ms 15004 KB Output is correct
20 Correct 203 ms 10244 KB Output is correct
21 Correct 199 ms 10292 KB Output is correct
22 Execution timed out 3015 ms 14144 KB Time limit exceeded
23 Halted 0 ms 0 KB -