Submission #740304

#	Time	Username	Problem	Language	Result	Execution time	Memory
740304		bgnbvnbv	Senior Postmen (BOI14_postmen)	C++14	55 / 100	659 ms	77956 KiB

postmen

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m;
struct qdge
{
    ll u,v;
}e[maxN];
vector<ll>g[maxN];
bool ex[maxN],in[maxN];
ll deg[maxN];
set<int>s;
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> e[i].u >> e[i].v;
        g[e[i].u].pb(i);
        g[e[i].v].pb(i);
        ex[i]=true;
        deg[e[i].u]++;
        deg[e[i].v]++;
    }
    for(int i=1;i<=n;i++) in[i]=false,s.insert(i);
    while(s.size()>0)
    {
        vector<pli>q;
        q.pb({*s.begin(),0});
        in[*s.begin()]=true;
        while(q.size()>0)
        {
            ll u=q.back().fi;
            while(g[u].size()>0&&ex[g[u].back()]==false) g[u].pop_back();
            if(g[u].size()>0)
            {
                ll id=g[u].back();
                ll v=u^e[id].u^e[id].v;
                ex[id]=false;
                if(in[v]==true)
                {
                    while(true)
                    {
                        ll x=q.back().fi;
                        ll vd=q.back().se;
                        q.pop_back();
                        cout << x<<' ';
                        deg[x]-=2;
                        if(deg[x]==0) s.erase(x);
                        in[x]=false;
                        if(x==v)
                        {
                            if(q.size()>0)
                            {
                                in[v]=true;
                                q.pb({x,vd});
                            }
                            break;
                        }
                    }
                    cout << '\n';
                }
                else
                {
                    in[v]=true;
                    q.push_back({v,id});
                }
            }
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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