Submission #1072825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072825		12345678	Fun Tour (APIO20_fun)	C++17	0 / 100	2 ms	2792 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int vs[nx], rt, pa[nx], deg[nx], h[nx];
vector<int> d[nx], res;
priority_queue<pair<int, int>> pql, pqr;

void dfs(int u)
{
    if (!vs[pa[u]]&&pa[u]!=rt) deg[pa[u]]++;
    for (auto v:d[u]) if (!vs[v]) h[v]=h[u]+1, dfs(v);
}

void dfsfill(int u, priority_queue<pair<int, int>> &pq)
{
    if (deg[u]==0) pq.push({h[u], u});
    for (auto v:d[u]) if (!vs[v]) dfsfill(v, pq);
}

std::vector<int> createFunTour(int N, int Q) {
    for (int i=1; i<N; i++) d[(i-1)/2].push_back(i), pa[i]=(i-1)/2;
    rt=0;
    while (1)
    {
        int cnt=0;
        for (auto x:d[rt]) if (!vs[x]) cnt++;
        if (cnt==0) 
        {
            res.push_back(rt);
            break;
        }
        if (cnt==1)
        {
            res.push_back(rt);
            vs[rt]=1;
            for (auto x:d[rt]) 
            {
                if (!vs[x]);
                rt=x;
                break;
            }
            continue;
        }
        if (cnt==2)
        {
            for (int i=0; i<N; i++) deg[i]=0;
            dfs(d[rt][0]);
            dfsfill(d[rt][0], pql);
            dfs(d[rt][1]);
            dfsfill(d[rt][1], pqr);
            if (pql.top().first<pqr.top().first) swap(pql, pqr);
            while (!pql.empty())
            {
                auto [_, u]=pql.top();
                pql.pop();
                res.push_back(u);
                vs[u]=1;
                if (pa[u]!=rt) --deg[pa[u]];
                if (pa[u]!=rt&&deg[pa[u]]==0) pql.push({h[pa[u]], pa[u]});
                swap(pql, pqr);
            }
            res.push_back(rt);
            vs[rt]=1;
            int nrt=-1;
            cnt=0;
            for (auto x:d[rt]) if (!vs[x]) nrt=x;
            if (nrt==-1) break;
            rt=nrt;
        }
    }
    /*
    cout<<"res : ";
    for (auto x:res) cout<<x<<' ';
    cout<<'\n';
    */
    return res;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34