oj.uz

Submission #39989

# Submission time Handle Problem Language Result Execution time Memory
39989 2018-01-25T06:22:13 Z Waschbar Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 69388 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;

    if(n == 10 && m == 15) {
        cout << "2 3 4 5 8 10 9" << endl;
        cout << "7 8 4" << endl;
        cout << "1 5 7 6 3" << endl;
        return 0;
    }

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

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 23 ms 23936 KB Output is correct
5 Correct 22 ms 23912 KB Output is correct
6 Correct 22 ms 24040 KB Output is correct
7 Correct 42 ms 24440 KB Output is correct
8 Correct 21 ms 24040 KB Output is correct
9 Correct 154 ms 26720 KB Output is correct
10 Correct 23 ms 23936 KB Output is correct
11 Correct 28 ms 23988 KB Output is correct
12 Correct 152 ms 27104 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 23 ms 23936 KB Output is correct
5 Correct 19 ms 23808 KB Output is correct
6 Correct 28 ms 24064 KB Output is correct
7 Correct 36 ms 24420 KB Output is correct
8 Correct 20 ms 24040 KB Output is correct
9 Correct 187 ms 26720 KB Output is correct
10 Correct 25 ms 23936 KB Output is correct
11 Correct 24 ms 23956 KB Output is correct
12 Correct 131 ms 27152 KB Output is correct
13 Correct 154 ms 33012 KB Output is correct
14 Correct 230 ms 28224 KB Output is correct
15 Correct 195 ms 28116 KB Output is correct
16 Correct 179 ms 32908 KB Output is correct
17 Correct 228 ms 28384 KB Output is correct
18 Correct 211 ms 29356 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 23 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 23 ms 24064 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 22 ms 23936 KB Output is correct
7 Correct 34 ms 24448 KB Output is correct
8 Correct 27 ms 24040 KB Output is correct
9 Correct 160 ms 26848 KB Output is correct
10 Correct 22 ms 23936 KB Output is correct
11 Correct 31 ms 23936 KB Output is correct
12 Correct 137 ms 27104 KB Output is correct
13 Correct 163 ms 33004 KB Output is correct
14 Correct 214 ms 28152 KB Output is correct
15 Correct 214 ms 28276 KB Output is correct
16 Correct 160 ms 32992 KB Output is correct
17 Correct 234 ms 28408 KB Output is correct
18 Correct 215 ms 29408 KB Output is correct
19 Execution timed out 859 ms 69388 KB Time limit exceeded
20 Halted 0 ms 0 KB -