oj.uz

Submission #39988

# Submission time Handle Problem Language Result Execution time Memory
39988 2018-01-25T06:08:48 Z Waschbar Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 69476 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() {

    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 << 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:64: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 19 ms 23808 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 25 ms 23936 KB Output is correct
5 Correct 20 ms 23896 KB Output is correct
6 Correct 23 ms 24040 KB Output is correct
7 Correct 35 ms 24560 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 109 ms 26720 KB Output is correct
10 Correct 20 ms 24064 KB Output is correct
11 Correct 22 ms 24040 KB Output is correct
12 Correct 77 ms 27104 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 26 ms 23784 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 23 ms 24040 KB Output is correct
5 Correct 17 ms 23936 KB Output is correct
6 Correct 21 ms 24040 KB Output is correct
7 Correct 40 ms 24500 KB Output is correct
8 Correct 19 ms 24064 KB Output is correct
9 Correct 114 ms 26744 KB Output is correct
10 Correct 23 ms 23936 KB Output is correct
11 Correct 22 ms 23936 KB Output is correct
12 Correct 83 ms 27128 KB Output is correct
13 Correct 108 ms 33024 KB Output is correct
14 Correct 161 ms 28128 KB Output is correct
15 Correct 177 ms 28280 KB Output is correct
16 Correct 103 ms 33008 KB Output is correct
17 Correct 164 ms 28408 KB Output is correct
18 Correct 153 ms 29408 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 20 ms 23836 KB Output is correct
4 Correct 22 ms 23936 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 21 ms 23936 KB Output is correct
7 Correct 29 ms 24448 KB Output is correct
8 Correct 19 ms 24064 KB Output is correct
9 Correct 117 ms 26744 KB Output is correct
10 Correct 24 ms 24064 KB Output is correct
11 Correct 20 ms 23940 KB Output is correct
12 Correct 79 ms 27128 KB Output is correct
13 Correct 107 ms 33008 KB Output is correct
14 Correct 139 ms 28140 KB Output is correct
15 Correct 154 ms 28140 KB Output is correct
16 Correct 95 ms 33008 KB Output is correct
17 Correct 162 ms 28472 KB Output is correct
18 Correct 151 ms 29440 KB Output is correct
19 Execution timed out 528 ms 69476 KB Time limit exceeded
20 Halted 0 ms 0 KB -