oj.uz

Submission #39995

# Submission time Handle Problem Language Result Execution time Memory
39995 2018-01-25T07:11:03 Z Waschbar Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 89044 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;
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

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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 21 ms 23784 KB Output is correct
4 Correct 24 ms 23936 KB Output is correct
5 Correct 24 ms 23852 KB Output is correct
6 Correct 22 ms 24040 KB Output is correct
7 Correct 40 ms 24344 KB Output is correct
8 Correct 26 ms 24112 KB Output is correct
9 Correct 154 ms 26860 KB Output is correct
10 Correct 30 ms 24064 KB Output is correct
11 Correct 33 ms 24064 KB Output is correct
12 Correct 135 ms 27108 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 22 ms 23936 KB Output is correct
5 Correct 20 ms 23936 KB Output is correct
6 Correct 25 ms 23936 KB Output is correct
7 Correct 34 ms 24448 KB Output is correct
8 Correct 21 ms 24192 KB Output is correct
9 Correct 160 ms 26756 KB Output is correct
10 Correct 24 ms 23936 KB Output is correct
11 Correct 26 ms 24032 KB Output is correct
12 Correct 136 ms 27128 KB Output is correct
13 Correct 170 ms 36892 KB Output is correct
14 Correct 204 ms 28764 KB Output is correct
15 Correct 209 ms 28652 KB Output is correct
16 Correct 181 ms 36884 KB Output is correct
17 Correct 228 ms 28920 KB Output is correct
18 Correct 247 ms 30828 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 18 ms 23808 KB Output is correct
3 Correct 18 ms 23860 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 20 ms 23936 KB Output is correct
6 Correct 27 ms 24064 KB Output is correct
7 Correct 36 ms 24416 KB Output is correct
8 Correct 25 ms 24128 KB Output is correct
9 Correct 148 ms 26744 KB Output is correct
10 Correct 27 ms 23936 KB Output is correct
11 Correct 24 ms 24036 KB Output is correct
12 Correct 139 ms 27172 KB Output is correct
13 Correct 164 ms 36896 KB Output is correct
14 Correct 201 ms 28792 KB Output is correct
15 Correct 210 ms 28652 KB Output is correct
16 Correct 174 ms 36944 KB Output is correct
17 Correct 230 ms 28920 KB Output is correct
18 Correct 218 ms 30728 KB Output is correct
19 Execution timed out 876 ms 89044 KB Time limit exceeded
20 Halted 0 ms 0 KB -