Submission #704191

#	Time	Username	Problem	Language	Result	Execution time	Memory
704191		boyliguanhan	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1087 ms	23244 KiB

postmen

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
vector<pair<int, int>> adj[500100];
bitset<500100> removed;
int deg[500100];
stack<int> sol;
int read(){
    int res = 0, c = getchar_unlocked();
    while(c < '0' || c > '9')
        c = getchar_unlocked();
    while(isdigit(c))
        res = res*10+c - 48, c = getchar_unlocked();
    return res;
}
void reverse(){
    stack<int> temp;
    while(sol.size())
        temp.push(sol.top()), sol.pop();
    sol = temp;
}
void print(){
    stack<int> now;
    bitset<500100> appeared;
    while(sol.size()){
        if(appeared[sol.top()]){
            printf("%d", sol.top());
            while(now.top()!=sol.top())
                printf(" %d", now.top()), appeared[now.top()] = 0, now.pop();
            printf("\n");
        } else {
            appeared[sol.top()] = 1;
            now.push(sol.top());
        }
        sol.pop();
    }
}
void dfs(int n){
    for(auto i: adj[n])
        if(!removed[i.second])
            removed[i.second] = 1, dfs(i.first);
    sol.push(n);
}
int main(){
    int n = read(), m = read();
    for(int i = 0; i < m; i++) {
        int a = read(), b = read();
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        deg[a]++;
        deg[b]++;
    }
    dfs(1);
    reverse();
    print();
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:45:9: warning: unused variable 'n' [-Wunused-variable]
   45 |     int n = read(), m = read();
      |         ^

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