Submission #11147

#	Time	Username	Problem	Language	Result	Execution time	Memory
11147		tncks0121	어르신 집배원 (BOI14_postmen)	C++14	55 / 100	1036 ms	101224 KiB

postmen

//
//  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;
lit processed[N_][2];
bool first[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;
            auto &it = processed[cur][0];
            auto &it2 = processed[cur][1];
            if(!first[cur]) {
                first[cur] = true;
                it = gph[cur].begin();
                it2= edge[cur].begin();
            }
            for(; 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;
            }
            /*
            processed[cur][0] = it;
            processed[cur][1] = it2;*/
            if(!updated && !stk.empty()) stk.pop();
        }
    }
    
    
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:51: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:53: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 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45