Submission #1205627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205627		12345678	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	166 ms	8104 KiB

incursion

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

using namespace std;

const int nx=5e4+5;

int n, c[nx], sz[nx], dp[nx], pa[nx], vs[nx];
vector<int> d[nx], cn;
int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p) sz[u]+=dfssz(v, u);
    return sz[u];
}

void findcentroid(int u, int p, int rtsz)
{
    c[u]=1;
    for (auto v:d[u]) if (v!=p&&2*sz[v]>rtsz) c[u]=0;
    if (2*(n-sz[u])>rtsz) c[u]=0;
    for (auto v:d[u]) if (v!=p) findcentroid(v, u, rtsz);
    if (c[u]) cn.push_back(u);
}

void dfs(int u, int p, int safe)
{
    sz[u]=1;
    if (safe==u) dp[u]=1;
    if (u!=p) pa[u]=p;
    for (auto v:d[u]) if (v!=p&&!c[v]) dfs(v, u, safe), dp[u]|=dp[v], sz[u]+=sz[v];
}

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    cn.clear();
    n=F.size()+1;
    for (int i=1; i<=n; i++) d[i].clear(), c[i]=dp[i]=sz[i]=0;
    for (auto [u, v]:F) d[u].push_back(v), d[v].push_back(u);
    findcentroid(1, 1, dfssz(1, 1));
    for (int i=1; i<=n; i++) if (c[i]) dfs(i, i, safe);
    vector<int> res;
    for (int i=1; i<=n; i++) res.push_back(dp[i]);
    return res; 
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
    n=F.size()+1;
    cn.clear();
    for (int i=1; i<=n; i++) d[i].clear(), c[i]=dp[i]=sz[i]=pa[i]=vs[i]=0;
    for (auto [u, v]:F) d[u].push_back(v), d[v].push_back(u);
    findcentroid(1, 1, dfssz(1, 1));
    if (cn.size()==2) pa[cn[0]]=cn[1], pa[cn[1]]=cn[0];
    //for (int i=1; i<=n; i++) cout<<"cen "<<i<<' '<<c[i]<<'\n';
    for (int i=1; i<=n; i++) if (c[i]) dfs(i, i, 0);
    //for (int i=1; i<=n; i++) cout<<"pa "<<i<<' '<<pa[i]<<'\n';
    while (1)
    {
        vs[curr]=1;
        if (t==0) t=visit(pa[curr]), curr=pa[curr];
        else
        {
            vector<pair<int, int>> hv;
            for (auto v:d[curr]) if (v!=pa[curr]) hv.push_back({sz[v], v});
            sort(hv.begin(), hv.end());
            reverse(hv.begin(), hv.end());
            int f=1;
            for (auto [sz, v]:hv)
            {
                if (vs[v]) continue;
                auto nt=visit(v);
                if (nt)
                {
                    f=0;
                    curr=v;
                    t=nt;
                    break;
                }
                visit(curr);
            }
            if (f) return;
        }
    }
}

/*
5 4
1 2
2 4
2 3
4 5

6 2
1 2
2 3
2 4
4 5
4 6
*/

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40