Submission #39995

#	Time	Username	Problem	Language	Result	Execution time	Memory
39995		Waschbar	Senior Postmen (BOI14_postmen)	C++14	55 / 100	876 ms	89044 KiB

postmen

#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;

const int INF = 1e8;
const int MOD = 1e9+7;
const int MAXN = 500000;

int n, m, t;
int pr[MAXN+1], rd[MAXN+1];
bool used[MAXN+1], vis[MAXN+1];
vector < vector < int > > ans(MAXN+1);
vector < vector < pair<int,int> > > g(MAXN+1);

int DFS(int f, int p) {
        pr[f] = p;

        for(int i = 0; i < g[f].size(); i++) {
            int to = g[f][i].first;
            int num = g[f][i].second;
            if(to == p || vis[num] != 0) continue;
            if(used[to]) {
                t++;
                int x = f;
                vis[num] = 1;
                while(x != to){
                    used[x] = 0;
                    vis[rd[x]] = 1;
                    ans[t].push_back(x);
                    x = pr[x];
                }
                    ans[t].push_back(x);
                return to;
            }
            used[f] = 1;
            rd[to] = num;
            int x = DFS(to,f);
            if(x != f) return x;
        }

        used[f] = 0;
        return -1;
}

int main() {

    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back({y,i});
        g[y].push_back({x,i});
    }

    t = 0;
    for(int i = 1; i <= n; i++)
        DFS(i,0);

    for(int i = 1; i <= t; i++) {
        for(int j = 0; j < ans[i].size(); j++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
}

Compilation message (stderr)

postmen.cpp: In function 'int DFS(int, int)':
postmen.cpp:19:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < g[f].size(); i++) {
                        ~~^~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:62:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < ans[i].size(); j++)
                        ~~^~~~~~~~~~~~~~~

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45