Submission #97101

#	Time	Username	Problem	Language	Result	Execution time	Memory
97101		dalgerok	Senior Postmen (BOI14_postmen)	C++14	100 / 100	489 ms	55284 KiB

postmen

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


const int N = 5e5 + 5;


int n, m, x[N], y[N];
vector < int > g[N], q1, q2;
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);
    }
    q1.push_back(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));
    for(int i = 0; i < (int)q1.size(); i++){
        int it = q1[i];
        if(!used[it]){
            used[it] = true;
            q2.push_back(it);
        }
        else{
            while(q2.back() != it){
                print(q2.back());
                putchar_unlocked(' ');
                used[q2.back()] = false;
                q2.pop_back();
            }
            print(it);
            putchar_unlocked('\n');
        }
    }
}

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