Submission #1072881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072881		12345678	Fun Tour (APIO20_fun)	C++17	47 / 100	409 ms	97592 KiB

fun

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

using namespace std;

const int nx=1e5+5;

int rt, pa[nx], lvl[nx], vs[nx];
vector<int> d[nx], res;
set<pair<int, int>> s[nx];
pair<int, int> mx;

pair<int, int> getmax(int x)
{
    if (s[x].empty()) return {-1, -1};
    return *(prev(s[x].end()));
}

void findmax(int x)
{
    auto tmp=getmax(x);
    tmp.first-=lvl[x];
    mx=max(mx, tmp);
    int u=x;
    while (u!=0)
    {
        int t=pa[u];
        for (auto v:d[t]) 
        {
            if (v==u) continue;
            pair<int, int> tmp=getmax(v);
            tmp.first-=lvl[v];
            tmp.first+=lvl[x]-lvl[t]+1;
            mx=max(mx, tmp);
        }
        u=t;
        if (s[u].find({lvl[u], u})!=s[u].end()) mx=max(mx, {lvl[x]-lvl[u], u});
    }
}

void addnode(int x)
{
    int u=x;
    s[u].insert({lvl[u], u});
    while (u!=0) u=pa[u], s[u].insert({lvl[x], x});
}

void erasenode(int x)
{
    int u=x;
    s[u].erase({lvl[u], u});
    while (u!=0) u=pa[u], s[u].erase({lvl[x], x});
}

void dfs(int u, int p, int w)
{
    mx=max(mx, {w, u});
    for (auto v:d[u]) if (v!=p&&!vs[v]) dfs(v, u, w+1);
}

int find(int x)
{
   mx={-1, 0};
   dfs(x, x, 0);
   return mx.second;
}

std::vector<int> createFunTour(int N, int Q) {
    if (N>500)
    {
    for (int i=1; i<N; i++) d[(i-1)/2].push_back(i), pa[i]=(i-1)/2, lvl[i]=lvl[pa[i]]+1;
    for (int i=0; i<N; i++) addnode(i);
    rt=N-1;
    res.push_back(rt);
    erasenode(rt);
    for (int i=1; i<N; i++)
    {
        //cout<<"rt "<<rt<<'\n';
        mx={-1, -1};
        findmax(rt);
        //cout<<mx.first<<' '<<mx.second<<'\n';
        res.push_back(mx.second);
        erasenode(mx.second);
        rt=mx.second;
    }
    /*
    cout<<"res : ";
    for (auto x:res) cout<<x<<' ';
    cout<<'\n';
    */
    return res;
    }
    else
    {
        for (int i=0; i<N; i++) for (int j=i+1; j<N; j++) if (hoursRequired(i, j)==1) d[i].push_back(j), d[j].push_back(i);
    rt=find(0);
    res.push_back(rt);
    vs[rt]=1;
    for (int i=1; i<N; i++) rt=find(rt), vs[rt]=1, res.push_back(rt);
    return res;
    }
}

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