Submission #1069125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069125		vjudge1	Pipes (CEOI15_pipes)	C++17	20 / 100	493 ms	65540 KiB

pipes

#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];

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; 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);
        if(y > z){
            swap(d[i].fi, d[i].se);
        }
    }
    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;
        }
    }
    for(int i = 0; i < d.size(); ++i){
        if(bridges[i] == 1){
            cout << d[i].fi << " " << d[i].se << endl;
        }
    }
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10