Submission #754210

#	Time	Username	Problem	Language	Result	Execution time	Memory
754210		phoebe	Senior Postmen (BOI14_postmen)	C++17	100 / 100	484 ms	70748 KiB

postmen

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

#pragma GCC optimize("03")

#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 5e5 + 10;
int n, m, to_parent[maxn], parent[maxn], rem[maxn] = {0}, idx[maxn] = {0};
pii edge[maxn];
bool seen[maxn] = {0}, deleted[maxn] = {0};
vector<pii> adj[maxn];

void dfs(int start){
    stack<int> s;
    s.push(start); 
    while (!s.empty()){
        int v = s.top(); seen[v] = true;
        while (idx[v] < adj[v].size()){
            int u = adj[v][idx[v]].F, i = adj[v][idx[v]].S; idx[v]++;
            if (deleted[i] || u == parent[v]){
                continue;
            }
            if (!seen[u]){
                parent[u] = v; to_parent[u] = i;
                s.push(u); break;
            }
            rem[v]--; rem[u]--; deleted[i] = true;
            while (s.top() != u){
                cout << s.top() << ' ';
                rem[s.top()]--; rem[parent[s.top()]]--; 
                deleted[to_parent[s.top()]] = true;
                seen[s.top()] = false; s.pop();
            }
            cout << u << endl;
            if (rem[u] == 0) s.pop();
            break;
        }
    }
}

signed main(){
    NYOOM;
    cin >> n >> m;
    FOR(i, m){
        int u, v; cin >> u >> v; edge[i] = {u, v};
        rem[u]++; rem[v]++;
        adj[u].PB({v, i}); adj[v].PB({u, i});
    }
    for (int v = 1; v <= n; v++){
        while (rem[v] > 0) dfs(v);
    }
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(long long int)':
postmen.cpp:30:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while (idx[v] < adj[v].size()){
      |                ~~~~~~~^~~~~~~~~~~~~~~

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