Submission #740310

#	Time	Username	Problem	Language	Result	Execution time	Memory
740310		bgnbvnbv	Senior Postmen (BOI14_postmen)	C++14	100 / 100	488 ms	43940 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=int;
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];
}
vector<ll>q;
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)
    {
        q.pb(nxt[0]);
        in[nxt[0]]=true;
        while(q.size()>0)
        {
            ll u=q.back();
            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();
                        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);
                            }
                            break;
                        }
                    }
                    cout << '\n';
                }
                else
                {
                    in[v]=true;
                    q.push_back(v);
                }
            }
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

postmen.cpp:11:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const ll inf=1e18;
      |              ^~~~

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