제출 #399018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399018		lyc	어르신 집배원 (BOI14_postmen)	C++14	100 / 100	274 ms	66360 KiB

postmen

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
typedef pair<int,int> ii;

const int mxN = 5e5+5;
const int mxM = 5e5+5;

int N, M;
struct Edge { int v, i, n; } el[2*mxM];
int al[mxN];
bool vis[mxN];
bool used[mxM];

vector<int> cyc;
void dfs(int u) {
    if (vis[u]) {
        int v;
        do {
            v = cyc.back();
            cout << v << ' ';
            cyc.pop_back();
            vis[v] = 0;
        } while (v != u);
        cout << '\n';
    }

    cyc.push_back(u);
    vis[u] = 1;
    while (al[u] > 0) {
        Edge e = el[al[u]];
        al[u] = e.n;
        if (!used[e.i]) {
            used[e.i] = 1;
            dfs(e.v);
            break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> N >> M;
    FOR(i,1,M){
        int U, V; cin >> U >> V;
        el[2*i-1] = (Edge){V,i,al[U]};
        el[2*i] = (Edge){U,i,al[V]};
        al[U] = 2*i-1;
        al[V] = 2*i;
    }

    FOR(i,1,N){
        dfs(i);
        while (SZ(cyc)) {
            vis[cyc.back()] = 0;
            cyc.pop_back();
        }
    }
}

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