Submission #97100

#	Time	Username	Problem	Language	Result	Execution time	Memory
97100		dalgerok	Senior Postmen (BOI14_postmen)	C++14	100 / 100	455 ms	55376 KiB

postmen

#include<bits/stdc++.h>
using namespace std;


const int N = 5e5 + 5;


int n, m, x[N], y[N], a[3 * N], sz;
vector < int > g[N];
bool used[N];
vector < int > q;


void dfs(int v){
    while(!g[v].empty()){
        int num = g[v].back();
        g[v].pop_back();
        if(used[num]){
            continue;
        }
        used[num] = true;
        int to = (x[num] ^ v ^ y[num]);
        dfs(to);
    }
    a[++sz] = v;
}

inline void read(int &x){
    x = 0;
    char c = getchar_unlocked();
    while(c < '0' || c > '9'){
        c = getchar_unlocked();
    }
    while('0' <= c && c <= '9'){
        x = x * 10 + c - '0';
        c = getchar_unlocked();
    }
}
inline void print(int x){
    int len = 0;
    while(x % 10 == 0){
        len += 1;
        x /= 10;
    }
    int y = 0;
    while(x){
        y = y * 10 + x % 10;
        x /= 10;
    }
    while(y){
        putchar_unlocked('0' + y % 10);
        y /= 10;
    }
    while(len--){
        putchar_unlocked('0');
    }
}

int main(){
    read(n);
    read(m);
    for(int i = 1; i <= m; i++){
        read(x[i]);
        read(y[i]);
        g[x[i]].push_back(i);
        g[y[i]].push_back(i);
    }
    dfs(1);
    memset(used, 0, sizeof(used));
    vector < int > s;
    for(int i = 1; i <= sz; i++){
        int it = a[i];
        if(!used[it]){
            used[it] = true;
            s.push_back(it);
        }
        else{
            while(s.back() != it){
                print(s.back());
                putchar_unlocked(' ');
                used[s.back()] = false;
                s.pop_back();
            }
            print(it);
            putchar_unlocked('\n');
        }
    }
}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45