Submission #11150

#	Time	Username	Problem	Language	Result	Execution time	Memory
11150		tncks0121	Senior Postmen (BOI14_postmen)	C++14	100 / 100	447 ms	18456 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_ = 2 * 500050;
 
int N, M;
 
bool passed[M_];
bool visited[N_];
int con[M_], lnk[M_], beg[N_], E;
int processed[N_];
 stack<int> stk; 
int main() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        int u, v; scanf("%d%d", &u, &v);
         
        ++E; lnk[E] = beg[u]; beg[u] = E; con[E] = v;
        ++E; lnk[E] = beg[v]; beg[v] = E; con[E] = u;
    }
     
    memset(processed, -1, sizeof processed);
     
    for(int u = 1; u <= N; u++) {
        stk.push(u);
         
        while(!stk.empty()) {
            int cur = stk.top();
            visited[cur] = true;
             
            int &i = processed[cur];
            if(i < 0) i = beg[cur];
             
            bool updated = false;
            for(; i > 0; i = lnk[i]) {
                int nxt = con[i];
                int e = (i-1)/2+1; 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 (stderr)

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: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45