Submission #39986

#	Time	Username	Problem	Language	Result	Execution time	Memory
39986		Waschbar	Senior Postmen (BOI14_postmen)	C++14	55 / 100	548 ms	69480 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;
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) {
        used[f] = 1;

        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]) continue;
            if(used[to]) {
                vis[num] = 1;
                used[f] = 0;
                ans[++t].push_back(f);
                return to;
            }
            else{
                int x = DFS(to,f);
                if(x == -1) continue;
                vis[num] = 1;
                ans[t].push_back(f);
                if(f != x) {
                    used[f] = 0;
                    return x;
                }
            }
        }

        return -1;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    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});
    }

    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 << "\n";
    }

}

Compilation message (stderr)

postmen.cpp: In function 'int DFS(int, int)':
postmen.cpp:18: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:63: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