Submission #1061990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061990		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	2904 KiB

oneway

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

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