oj.uz

Submission #11145

# Submission time Handle Problem Language Result Execution time Memory
11145 2014-11-15T02:30:06 Z tncks0121 Senior Postmen (BOI14_postmen) C++14
38 / 100
 500 ms 31360 KB 
//
//  main.cpp
//  BOI14_postmen
//
//  Created by 박수찬 on 14. 11. 14..
//  Copyright (c) 2014년 박수찬. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 500050, M_ = 500050;

int N, M;
vector<int> gph[N_];
vector<int> edge[N_];
bool passed[M_];
bool visited[N_];

int main() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        int u, v; scanf("%d%d", &u, &v);
        gph[u].push_back(v);
        gph[v].push_back(u);
        edge[u].push_back(i);
        edge[v].push_back(i);
    }
    
    for(int u = 1; u <= N; u++) {
        stack<int> stk; stk.push(u);
        
        while(!stk.empty()) {
            int cur = stk.top();
            visited[cur] = true;
            
            bool updated = false;
            for(int i = 0; i < gph[cur].size(); i++) {
                int nxt = gph[cur][i];
                int e = edge[cur][i]; if(passed[e]) continue;
                passed[e] = true;
                if(visited[nxt]) {
                    while(!stk.empty() && stk.top() != nxt) {
                        int vt = stk.top(); stk.pop();
                        visited[vt] = false;
                        printf("%d ", vt);
                    }
                    printf("%d\n", nxt);
                } else {
                    stk.push(nxt);
                }
                updated = true;
                break;
            }
            
            if(!updated && !stk.empty()) stk.pop();
        }
    }
    
    
    return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:64:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < gph[cur].size(); i++) {
                            ~~^~~~~~~~~~~~~~~~~
postmen.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:49:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23808 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 20 ms 23784 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 18 ms 23924 KB Output is correct
6 Correct 20 ms 23936 KB Output is correct
7 Correct 32 ms 24320 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 82 ms 26232 KB Output is correct
10 Correct 22 ms 24064 KB Output is correct
11 Correct 20 ms 23936 KB Output is correct
12 Correct 72 ms 26616 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 18 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 22 ms 23808 KB Output is correct
6 Correct 27 ms 23936 KB Output is correct
7 Correct 26 ms 24368 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 87 ms 26232 KB Output is correct
10 Correct 23 ms 24064 KB Output is correct
11 Correct 27 ms 23936 KB Output is correct
12 Correct 74 ms 26616 KB Output is correct
13 Correct 173 ms 31360 KB Output is correct
14 Correct 124 ms 29304 KB Output is correct
15 Execution timed out 827 ms 29160 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 20 ms 23936 KB Output is correct
5 Correct 26 ms 23936 KB Output is correct
6 Correct 23 ms 23936 KB Output is correct
7 Correct 25 ms 24320 KB Output is correct
8 Correct 24 ms 23936 KB Output is correct
9 Correct 85 ms 26208 KB Output is correct
10 Correct 29 ms 24012 KB Output is correct
11 Correct 22 ms 23936 KB Output is correct
12 Correct 83 ms 26680 KB Output is correct
13 Correct 181 ms 31344 KB Output is correct
14 Correct 142 ms 29364 KB Output is correct
15 Execution timed out 957 ms 29184 KB Time limit exceeded
16 Halted 0 ms 0 KB -