oj.uz

Submission #39991

# Submission time Handle Problem Language Result Execution time Memory
39991 2018-01-25T06:27:41 Z Waschbar Senior Postmen (BOI14_postmen) C++14
0 / 100
 18 ms 23860 KB 
#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;
                }
            }
        }

        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

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:60:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < ans[i].size(); j++)
                        ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23860 KB Some edges were not used
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23808 KB Some edges were not used
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23816 KB Some edges were not used
2 Halted 0 ms 0 KB -