Submission #267072

#	Time	Username	Problem	Language	Result	Execution time	Memory
267072		ChrisT	Mountains and Valleys (CCO20_day1problem3)	C++17	25 / 25	3117 ms	206452 KiB

Main

#include <bits/stdc++.h>

using namespace std;

template<int K>
struct KMax
{
    pair<int, int> data[K];
    KMax()
    {
        reset();
    }
    void reset()
    {
        for(int i=0; i<K; i++)
            data[i]={-1, 0};
    }
    void insert(int k, int v)
    {
        for(int i=0; i<K; i++) if(data[i].second<v)
        {
            for(int j=K-2; j>=i; j--)
                data[j+1]=data[j];
            data[i]={k, v};
            break;
        }
    }
    int get(int ban, int k)
    {
        int ret=0;
        for(int i=0; i<K; i++) if(data[i].first!=ban)
        {
            ret+=data[i].second;
            if(--k==0)
                break;
        }
        return ret;
    }
    int get(int ban1, int ban2, int k)
    {
        int ret=0;
        for(int i=0; i<K; i++) if(data[i].first!=ban1 && data[i].first!=ban2)
        {
            ret+=data[i].second;
            if(--k==0)
                break;
        }
        return ret;
    }
};

struct edge
{
    int u, v, w;
};

int N;
vector<vector<int>> adj;
vector<edge> q, qb;
vector<int> qc;
vector<int> sz;
vector<int> depth;
vector<int> tin;
vector<int> invt;
int tnow;
vector<int> subtree;
vector<int> lpath; // longest path in this subtree
vector<int> lerased; // longest path from an erased subtree next to this, includes erased edge
vector<int> leraseddiam; // longest diameter from an erased subtree next to this
vector<int> ldiam; // longest diameter in this subtree
// type 0
//  . (. .) (c)
// (.)
// /|
vector<int > type0; // longest path off the main path
// type 1
// (- -) - (. .) . (c)
//       |
vector<int> type1;

void dfs_type012(int u, int p, int max_t0, int max_t1, int max_p2, int max_t2)
{
    type0[u]=max(max_t0, ldiam[u]);
    type1[u]=max(max_t1, lpath[u]);
    KMax<2> m2d;
    for(auto& v: adj[u]) if(v!=p)
        m2d.insert(v, ldiam[v]);
    KMax<3> m3;
    m3.insert(u, lerased[u]);
    for(auto& v: adj[u]) if(v!=p)
        m3.insert(v, lpath[v]+1);
    for(auto& v: adj[u]) if(v!=p)
    {
        int w=m3.get(v, 1);
        dfs_type012(v, u, max(max_t0, max(m2d.get(v, 1), m3.get(v, 2))),
                          max(max_t1, w)+1,
                          max(max_p2, w+depth[u]), max(max_t2, w+max_p2)+1);
    }
}

pair<int, int> dfs(int u, int p)
{
    pair<int, int> ret={u, 0};
    for(auto& v: adj[u]) if(v!=p)
    {
        int a, b;
        tie(a, b)=dfs(v, u);
        if(b+1>ret.second)
            ret={a, b+1};
    }
    return ret;
}

void dfs_sz(int u, int p)
{
    sz[u]=1;
    for(auto& v: adj[u]) if(v!=p)
    {
        dfs_sz(v, u);
        sz[u]+=sz[v];
    }
}

void dfs_t(int u, int p)
{
    tin[u]=tnow++;
    invt[tin[u]]=u;
    lpath[u]=lerased[u];
    ldiam[u]=leraseddiam[u];
    for(auto& v: adj[u]) if(v!=p)
    {
        depth[v]=depth[u]+1;
        dfs_t(v, u);
        lpath[u]=max(lpath[u], lpath[v]+1);
        ldiam[u]=max(ldiam[u], ldiam[v]);
    }
    KMax<2> m2;
    m2.insert(u, lerased[u]);
    for(auto& v: adj[u]) if(v!=p)
        m2.insert(v, lpath[v]+1);
    ldiam[u]=max(ldiam[u], m2.data[0].second+m2.data[1].second);
}

int get_centroid(int u)
{
    while(1)
    {
        int w=-1;
        for(auto& v: adj[u]) if(w==-1 || sz[v]>sz[w])
            w=v;
        if(w==-1 || sz[w]*2<=sz[u])
            break;
        sz[u]-=sz[w];
        sz[w]+=sz[u];
        u=w;
    }
    return u;
}

int solve(int u, int ql, int qr)
{
    if(ql==qr)
        return 0x3f3f3f3f;
    dfs_sz(u, u);
    u=get_centroid(u);
    tnow=0;
    depth[u]=0;
    dfs_t(u, u);
    int last=tin[u], lastu=u;
    for(auto& v: adj[u])
    {
        for(int i=last; i<tin[v]; i++)
            subtree[invt[i]]=lastu;
        last=tin[v];
        lastu=v;
    }
    for(int i=last; i<tnow; i++)
        subtree[invt[i]]=lastu;
    type0[u]=type1[u]=0;
    KMax<3> m3;
    KMax<4> m4;
    m4.insert(-1, lerased[u]);
    for(auto& v: adj[u])
    {
        qc[v]=0;
        m3.insert(v, ldiam[v]);
        m4.insert(v, lpath[v]+1);
        dfs_type012(v, u, 0, 0, 0, 0);
    }
    int qo=ql, qp=ql;
    int ret=0x3f3f3f3f;
    for(; ql<qr; ql++)
    {
        if(subtree[q[ql].u]==subtree[q[ql].v])
        {
            qc[subtree[q[ql].u]]++;
            q[qp++]=q[ql];
            continue;
        }
        int u=q[ql].u, v=q[ql].v, w=q[ql].w;
        // 3 cases:
        // 1. full cycle
        ret=min(ret, 2*(N-1+w)-depth[u]-depth[v]-w-max(max(type0[u], type0[v]), max(m3.get(subtree[u], subtree[v], 1), m4.get(subtree[u], subtree[v], 2))));
        // 2. partial cycle (gap on different sides)
        ret=min(ret, 2*(N-2+w)-w-type1[u]-type1[v]);
        // 3. partial cycle (gap on same side)
        // 3c. on u's side, v's end on centroid
        ret=min(ret, 2*(N-2+w)-w-type1[u]-depth[v]-m4.get(subtree[u], subtree[v], 1));
        // 3d. on v's side, u's end on centroid
        ret=min(ret, 2*(N-2+w)-w-type1[v]-depth[u]-m4.get(subtree[u], subtree[v], 1));
    }
    int qcs=0;
    for(auto& v: adj[u])
    {
        qcs+=qc[v];
        qc[v]=qcs;
    }
    for(int i=qo; i<qp; i++)
        qb[--qc[subtree[q[i].u]]]=q[i];
    for(int i=qo; i<qp; i++)
        q[i]=qb[i-qo];
    vector<pair<int, int>> ival;
    int l=qo, r;
    for(auto& v: adj[u])
    {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
        lerased[v]=max(lerased[v], m4.get(v, 1)+1);
        leraseddiam[v]=max(leraseddiam[v], max(lerased[v], max(m3.get(v, 1), m4.get(v, 2))));
        for(r=l; r<qp && subtree[q[r].u]==v; r++);
        ival.push_back({l, r});
        l=r;
    }
    for(int i=0; i<(int)adj[u].size(); i++)
        ret=min(ret, solve(adj[u][i], ival[i].first, ival[i].second));
    return ret;
}

int min_walk(int n, std::vector<int> x, std::vector<int> y, std::vector<int> w)
{
    N=n;
    int m=x.size();
    adj.resize(n);
    for(int i=0; i<m; i++) if(w[i]==1)
    {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    int ans=2*(n-1)-dfs(dfs(0, 0).first, -1).second;
    for(int i=0; i<m; i++) if(w[i]>1 && x[i]!=y[i])
        q.push_back({x[i], y[i], w[i]});
    qb.resize(q.size());
    qc.resize(n);
    sz.resize(n);
    depth.resize(n);
    tin.resize(n);
    invt.resize(n);
    subtree.resize(n);
    lpath.resize(n);
    lerased.resize(n);
    leraseddiam.resize(n);
    ldiam.resize(n);
    type0.resize(n);
    type1.resize(n);
    ans=min(ans, solve(0, 0, (int)q.size()));
    return ans;
}

int main()
{
    int n, m;
    ignore = scanf("%d%d", &n, &m);
    std::vector<int> x(m), y(m), w(m);
    for(int i=0; i<m; i++)
        ignore = scanf("%d%d%d", &x[i], &y[i], &w[i]);
    printf("%d\n", min_walk(n, x, y, w));
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 6 / 6
• Subtask 5: 2 / 2
• Subtask 6: 3 / 3
• Subtask 7: 5 / 5
• Subtask 8: 4 / 4