oj.uz

Submission #1000426

# Submission time Handle Problem Language Result Execution time Memory
1000426 2024-06-17T13:49:27 Z 12345678 JOI tour (JOI24_joitour) C++17
0 / 100
 274 ms 41840 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Incorrect 2 ms 19032 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Incorrect 2 ms 19032 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Incorrect 274 ms 41840 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19032 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Incorrect 3 ms 19032 KB Wrong Answer [1]
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19032 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Incorrect 2 ms 19032 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19032 KB Output is correct
3 Incorrect 2 ms 19032 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -