Submission #1072921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072921		12345678	Fun Tour (APIO20_fun)	C++17	0 / 100	4 ms	7516 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e5+5;
 
int rt, pa[nx], lvl[nx], n, rrt;
vector<int> res, d[nx];
set<pair<int, int>> s[nx];
pair<int, int> mx, hd;
 
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!=rrt)
    {
        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!=rrt) u=pa[u], s[u].insert({lvl[x], x});
}
 
void erasenode(int x)
{
    int u=x;
    s[u].erase({lvl[u], u});
    while (u!=rrt) u=pa[u], s[u].erase({lvl[x], x});
}
 
struct segtree
{
    pair<int, int> d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]={vl, idx}, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx,vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]); 
    }
    pair<int, int> query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return {INT_MIN, INT_MIN};
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} st;

void buildtree(int i, int l, int r)
{
    if (i!=l)
    {
        auto tmp=st.query(0, n-1, 1, l, i-1);
        d[i].push_back(tmp.second);
        pa[tmp.second]=i;
        lvl[tmp.second]=lvl[i]+1;
        buildtree(tmp.second, l, i-1);
    }
    if (i!=r)
    {
        auto tmp=st.query(0, n-1, 1, i+1, r);
        d[i].push_back(tmp.second);
        pa[tmp.second]=i;
        lvl[tmp.second]=lvl[i]+1;
        buildtree(tmp.second, i+1, r);
    }
}

std::vector<int> createFunTour(int N, int Q) {
    n=N;
    //for (int i=1; i<N; i++) if (attractionsBehind(rt, i)==N-i) rt=i;
    //cout<<"rt "<<rt<<'\n';
    rt=0;
    for (int i=0; i<N; i++) st.update(0, N-1, 1, i, attractionsBehind(rt, i));
    buildtree(rt, 0, N-1);
    rrt=rt;
    for (int i=0; i<N; i++) addnode(i);
    for (int i=0; i<N;i ++) mx=max(mx, {lvl[i], i});
    rt=mx.second;
    res.push_back(rt);
    erasenode(rt);
    for (int i=1; i<N; i++)
    {
        mx={-1, -1};
        findmax(rt);
        res.push_back(mx.second);
        erasenode(mx.second);
        rt=mx.second;
    }
    return res;
}

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