Submission #1000426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000426		12345678	JOI tour (JOI24_joitour)	C++17	0 / 100	274 ms	41840 KiB

joitour

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

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, t[nx], dp[3][nx], res, sz[nx], used[nx], pa[nx], rt, qs[3][nx], rem[nx];
vector<int> d[nx], c[nx];

int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
    return u; 
}

void decomposition(int u, int p)
{
    u=findcentroid(u, u, dfssz(u, u));
    used[u]=1;
    pa[u]=p;
    if (p==-1) rt=u;
    else c[p].push_back(u);
    for (auto v:d[u]) if (v!=p&&!used[v]) decomposition(v, u);
}

void dfs(int u)
{
    rem[u]=0;
    for (int i=0; i<3; i++) qs[i][u]=0;
    qs[t[u]][u]=1;
    for (auto v:c[u]) 
    {
        dfs(v);
        for (int i=0; i<3; i++) qs[i][u]+=qs[i][v];
    }
    if (pa[u]!=-1) rem[pa[u]]+=qs[0][u]*qs[2][u];
    if (t[u]==1) res+=qs[0][u]*qs[2][u]-rem[u];
}

void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) 
{
    n=N;
    for (int i=0; i<n; i++) t[i]=F[i];
    for (int i=0; i<n-1; i++) d[U[i]].push_back(V[i]), d[V[i]].push_back(U[i]);
    decomposition(0, -1);
}

void change(int X, int Y) 
{
    t[X]=Y;
}

long long num_tours() 
{
    res=0;
    dfs(rt);
    return res;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 34
• Subtask 7: 0 / 14