oj.uz

Submission #11146

# Submission time Handle Problem Language Result Execution time Memory
11146 2014-11-15T02:33:05 Z tncks0121 Senior Postmen (BOI14_postmen) C++14
0 / 100
 500 ms 36844 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 <list>
#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;
list<int> gph[N_];
list<int> edge[N_];
bool passed[M_];
bool visited[N_];
typedef list<int>::iterator  lit;

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(auto it = gph[cur].begin(), it2 = edge[cur].begin(); it != gph[cur].end(); it++, it2++) {
                int nxt = *it;
                int e = *it2; 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:49: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:51: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
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 30 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 25 ms 24256 KB Output is correct
5 Correct 23 ms 23936 KB Output is correct
6 Correct 23 ms 24448 KB Output is correct
7 Correct 55 ms 25720 KB Output is correct
8 Correct 23 ms 24064 KB Output is correct
9 Execution timed out 1084 ms 36740 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23772 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 24 ms 24192 KB Output is correct
5 Correct 20 ms 23936 KB Output is correct
6 Correct 29 ms 24424 KB Output is correct
7 Correct 46 ms 25696 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Execution timed out 1074 ms 36844 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 22 ms 23844 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 24 ms 24192 KB Output is correct
5 Correct 23 ms 23936 KB Output is correct
6 Correct 25 ms 24448 KB Output is correct
7 Correct 57 ms 25804 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Execution timed out 1066 ms 36748 KB Time limit exceeded
10 Halted 0 ms 0 KB -