Submission #1049624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049624		christinelynn	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1080 ms	44240 KiB

postmen

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

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

const int maxn=5e5;
set<int> adj[maxn+1];
int pre[maxn+1],x;
bool vis[maxn+1];

bool dfs(int v){
    vis[v]=1;
    for(int i:adj[v])if(i!=pre[v]){
        if(vis[i]){
            pre[i]=v;
            x=v;
            return 1;
        }else{
            pre[i]=v;
            if(dfs(i))return 1;
        }
    }
    return 0;
}

void solve() {
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].insert(v);
        adj[v].insert(u);
    }
    vector<vector<int>> ans;
    for(int i=1;i<=n;i++){
        while(!adj[i].empty()){
            memset(vis,0,sizeof(vis));
            pre[i]=0;
            dfs(i);
            ans.push_back({});
            ans.back().push_back(x);
            int c=x;
            while(pre[c]!=x){
                adj[c].erase(pre[c]);
                adj[pre[c]].erase(c);
                c=pre[c];
                ans.back().push_back(c);
            }
            adj[ans.back().back()].erase(ans.back()[0]);
            adj[ans.back()[0]].erase(ans.back().back());
        }
    }
    for(auto v:ans){
        for(int i:v)cout<<i<<' ';
        cout<<'\n';
    }
}

int main() {   
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

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