Submission #1000443

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1000443	2024-06-17 14:01:04	12345678	JOI tour (JOI24_joitour)	C++17	20 / 100	3097 ms	38788 KiB

joitour

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "joitour.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=2e5+5;
ll n, t[nx], cnt[3], dp[3][nx], res;
vector<int> d[nx];
void dfs(int u, int p)
{
    dp[0][u]=dp[1][u]=dp[2][u]=0;
    dp[t[u]][u]++;
    for (auto v:d[u]) if (v!=p) dfs(v, u), dp[0][u]+=dp[0][v], dp[1][u]+=dp[1][v], dp[2][u]+=dp[2][v];
    if (t[u]==1)
    {
        ll a=0, b=0;
        for (auto v:d[u])
        {
            if (v==p) continue;
            res+=dp[0][v]*b;
            res+=dp[2][v]*a;
            b+=dp[2][v];
            a+=dp[0][v];
        }
        //cout<<"here "<<u<<' '<<res<<'\n';
        res+=dp[0][u]*(cnt[2]-dp[2][u]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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