Submission #1262395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262395		aVe	Senior Postmen (BOI14_postmen)	C++20	0 / 100	10 ms	12616 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;
vector<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);
        }
    }
}*/

vector<int>v;

void dfs(int node,int par)
{
    for(auto ax:g[node])
    {
        int sosed=ax.first;
        int idx=ax.second;
        if(vis[idx] || sosed==par)continue;
        vis[idx]=1;
        dfs(sosed,node);
    }
    v.push_back(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_back({b,i});
        g[b].push_back({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());
    vector<vector<int>>ans;
    map<int,int>ma;
    vector<int>now;
    for(int i=0;i<v.size();i++)
    {
        v[i]++;
        now.push_back(v[i]);
        if(ma[now.back()]==1)
        {
            vector<int>A;
            A.push_back(now.back());
            now.pop_back();
            ma[now.back()]--;
            int j=i-1;
            while(j>=0)
            {
                if(now.back()==v[i])break;
                A.push_back(now.back());
                ma[v[j]]--;
                now.pop_back();
                j--;
            }
            ans.push_back(A);
        }
        else
        {
            ma[v[i]]++;
        }
    }
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
        {
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

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