Submission #743726

#	Time	Username	Problem	Language	Result	Execution time	Memory
743726		grogu	Senior Postmen (BOI14_postmen)	C++14	100 / 100	412 ms	88376 KiB

postmen

#include "bits/stdc++.h"
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define here cerr<<"---------------------------\n"
#define ceri(a,l,r) {for(ll i = l;i<=r;i++) cerr<<a[i]<< " ";cerr<<endl;}
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;

#define maxn 500005
vector<pll> g[maxn];
ll n,m;
bool vis[maxn];
vector<ll> ans;
ll it[maxn];
bool vis2[maxn];
void euler(ll u){
    vis2[u] = 1;
    while(it[u]<sz(g[u])){
      	pll p = g[u][it[u]];
        ll s = p.fi;
        ll j = p.sc;
        it[u]++;
        if(vis[j]) continue;
        vis[j] =1;
        euler(s);
    }
    ans.pb(u);
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m;
    for(ll i = 1;i<=m;i++){
        ll x,y; cin >> x >> y;
        g[x].pb({y,i});
        g[y].pb({x,i});
    }
    for(ll i = 1;i<=n;i++) if(!vis2[i]) euler(i);
    fill(vis,vis+maxn,0);
    vector<ll> v;
    vector<ll> w;
    for(ll x : ans){
        if(vis[x]==1){
            while(v.back()!=x){
                w.pb(v.back());
                v.popb();
            }
            w.pb(x);
            for(ll y : w){
                vis[y] = 0;
                cout<<y<< " ";
            }
            cout<<endl;
            w.clear();
            vis[x] = 1;
        }else vis[x] = 1,v.pb(x);
    }
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

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