Submission #1072913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072913		12345678	Fun Tour (APIO20_fun)	C++17	0 / 100	9 ms	14684 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e5+5;
 
int rt, pa[nx], lvl[nx], n;
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!=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});
}
 
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-1; i++) hd=max(hd, {attractionsBehind(i-1, i)+attractionsBehind(i+1, i), i});
    if (hd.first==N+1) rt=hd.second;
    else
    {
        if (hoursRequired(0, hd.second)!=1) rt=N-1;
        else if (hoursRequired(N-1, hd.second)!=1) rt=0;
        else
        {
            int tmp;
            for (int i=1; i<N-1; i++) if (hoursRequired(i, hd.second)==1) tmp=i;
            if (tmp<hd.second) rt=0;
            else rt=N-1;
        }
    }
    for (int i=0; i<N; i++) st.update(0, N-1, 1, i, attractionsBehind(rt, i));
    buildtree(rt, 0, N-1);
    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;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:108:13: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |             if (tmp<hd.second) rt=0;
      |             ^~

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