Submission #1262445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262445		aVe	Senior Postmen (BOI14_postmen)	C++20	0 / 100	142 ms	327680 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

///#define int long long

const int maxn=5e5+10;
const int mod=1e9+7;
const int logn=17;

int n,m;
stack<pair<int,int>>g[maxn];
///int deg[maxn];
bool vis[maxn];
///bool mark[maxn];

/*
void subtsz(int node,int par)
{
    dp[node]=1;
    for(auto ax:g[node])
    {
        if(vis[ax] || ax==par)continue;
        subtsz(ax,node);
        dp[node]=dp[ax]+1;
    }
}

int cen(int node,int par,int tsz)
{
    for(auto ax:g[node])
    {
        if(ax==par || vis[ax])continue;
        if(2*dp[ax]>tsz)///>=
        {
            return cen(ax,node,tsz);
        }
    }
    return node;
}

void b_c_d(int node,int par)
{
    subtsz(node,-1);///node za par
    int centroid=cen(node,-1,dp[node]);
    vis[centroid]=1;
    cen_par[centroid]=par;
    for(auto ax:g[centroid])
    {
        if(!vis[ax])
        {
            b_c_d(ax,centroid);
        }
    }
}*/

stack<int>v;
int ma[maxn];

void dfs(int node,int par)
{
    ///cout<<node<<endl;
    while(g[node].size()>0)
    {
        ///cout<<g[node].size()<<endl;
        int sosed=(g[node].top()).first;
        int idx=(g[node].top()).second;
        g[node].pop();
        if(vis[idx] || sosed==par)continue;
        ///g[node].pop();
        vis[idx]=1;
        dfs(sosed,node);
    }
    v.push(node);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        g[a].push({b,i});
        g[b].push({a,i});
        ///deg[a]++;
        ///deg[b]++;
    }
    /*for(int i=0;i<n;i++)
    {
        if(deg[i]%2==1)
        {
            cout<<-1<<endl;
            return 0;
        }
    }*/
    dfs(0,-1);
    ///reverse(v.begin(),v.end());
    stack<int>now;
    while(v.size()!=0)
    {
        int val=v.top()+1;
        now.push(val);
        if(ma[now.top()]==1)
        {
            ///vector<int>A;
            ///A.push_back(now.back());
            cout<<now.top()<<" ";
            now.pop();
            ///ma[now.back()]--;
            while(now.top()!=val)
            {
                //if(now.back()==v[i])break;
                ///A.push_back(now.back());
                cout<<now.top()<<" ";
                ma[now.top()]--;
                now.pop();
            }
            cout<<"\n";
            ///ans.push_back(A);
        }
        else
        {
            ma[val]++;
        }
        v.pop();
        ///cout<<now.size()<<endl;
    }
    /*for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
        {
            cout<<ans[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    return 0;
}

/*
while(g[node].size()>0)
    {
        int sosed=(g[node].top()).first;
        int idx=(g[node].top()).second;
        if(vis[idx] || sosed==par)continue;
        g[node].pop();
        vis[idx]=1;
        dfs(sosed,node);
    }
*/

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