Submission #740309

#	Time	Username	Problem	Language	Result	Execution time	Memory
740309		bgnbvnbv	Senior Postmen (BOI14_postmen)	C++14	55 / 100	543 ms	62356 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];
ll pre[maxN],nxt[maxN];
void xoa(ll x)
{
    pre[nxt[x]]=pre[x];
    nxt[pre[x]]=nxt[x];
}
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]++;
    }
    nxt[0]=1;
    pre[n+1]=n;
    for(int i=1;i<=n;i++) in[i]=false,pre[i]=i-1,nxt[i]=i+1;
    while(nxt[0]!=n+1)
    {
        vector<pli>q;
        q.pb({nxt[0],0});
        in[nxt[0]]=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) xoa(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