Submission #97097

#	Time	Username	Problem	Language	Result	Execution time	Memory
97097		dalgerok	Senior Postmen (BOI14_postmen)	C++14	55 / 100	575 ms	55308 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];
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);
    }
    q.push_back(v);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> x[i] >> 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(auto it : q){
        if(!used[it]){
            used[it] = true;
            s.push_back(it);
        }
        else{
            while(s.back() != it){
                cout << s.back() << " ";
                used[s.back()] = false;
                s.pop_back();
            }
            cout << it << "\n";
        }
    }
}

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