oj.uz

Submission #1011005

# Submission time Handle Problem Language Result Execution time Memory
1011005 2024-06-29T16:50:59 Z imarn JOI tour (JOI24_joitour) C++17
6 / 100
 1071 ms 197976 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn],f;
int sz[mxn]{0},lv[mxn]{0},pr[mxn];
bool vis[mxn]{0};
ll ans=0;
int getsz(int u,int p){
    sz[u]=1;
    for(auto v:g[u])if(v!=p&&!vis[v])sz[u]+=getsz(v,u);
    return sz[u];
}
int getct(int u,int p,int r){
    for(auto v:g[u])if(v!=p&&!vis[v]&&sz[v]*2>r)return getct(v,u,r);
    return u;
}
vector<ll>dp[6][mxn];
ll td[6][mxn]{0};
struct few{
    int fw[mxn]{0};
    void add(int i,int amt){
        for(;i<mxn;i+=i&-i)fw[i]+=amt;
    }
    ll qr(int i,ll res=0){
        for(;i;i-=i&-i)res+=fw[i];
        return res;
    }
}fw[3][19],wf[3][19];
int tin[19][mxn],tout[19][mxn],cnt[19]{0};
ll getP(int col,int lvl,int u){
    return fw[col][lvl].qr(tin[lvl][u]);
}
ll getC(int col,int lvl,int u){
    return wf[col][lvl].qr(tout[lvl][u])-wf[col][lvl].qr(tin[lvl][u]-1);
}
void gen1(int u,int p,int x,int id,int x0,int x1,int x2){
    dp[f[u]][x][id]++;tin[lv[x]][u]=++cnt[lv[x]];
    fw[0][lv[x]].add(tin[lv[x]][u],x0);
    fw[1][lv[x]].add(tin[lv[x]][u],x1);
    fw[2][lv[x]].add(tin[lv[x]][u],x2);
    if(f[u]==2)dp[3][x][id]+=x1;
    for(auto v:g[u])if(v!=p&&!vis[v])gen1(v,u,x,id,x0+(f[v]==0),x1+(f[v]==1),x2+(f[v]==2));
    tout[lv[x]][u]=cnt[lv[x]];
}
void gen2(int u,int p,int x,int id){
    for(auto v:g[u])if(v!=p&&!vis[v])gen2(v,u,x,id);
    wf[f[u]][lv[x]].add(tin[lv[x]][u],1);
    if(f[u]==1)dp[4][x][id]+=getC(0,lv[x],u);
}
void play(int u,int p){int id=-1;
    u = getct(u,u,getsz(u,u));vis[u]=1;
    pr[u]=p;if(p!=-1)lv[u]=lv[p]+1;
    tin[lv[u]][u]=++cnt[lv[u]];
    for(auto v:g[u]){
        if(vis[v])continue;
        for(int i=0;i<6;i++)dp[i][u].pb(0);id++;
        gen1(v,u,u,id,(f[v]==0),(f[v]==1),(f[v]==2));gen2(v,u,u,id);
        for(int i=0;i<6;i++)td[i][u]+=dp[i][u][id];
    }tout[lv[u]][u]=cnt[lv[u]];
    for(int j=0;j<=id;j++){
        ans+=dp[0][u][j]*(td[3][u]-dp[3][u][j]);
        ans+=dp[4][u][j]*(td[2][u]-dp[2][u][j]);
        if(f[u]==1)ans+=dp[0][u][j]*(td[2][u]-dp[2][u][j]);
    }if(f[u]==0)ans+=td[3][u];if(f[u]==2)ans+=td[4][u];
    for(auto v:g[u])if(!vis[v])play(v,u);
}
void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V,int Q){
    f=F;for(int i=0;i<N-1;i++)g[U[i]].pb(V[i]),g[V[i]].pb(U[i]);
    play(0,-1);
}

void change(int X, int Y) {}

long long num_tours() {
  return ans;
}

Compilation message

joitour.cpp: In function 'void play(int, int)':
joitour.cpp:69:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   69 |         for(int i=0;i<6;i++)dp[i][u].pb(0);id++;
      |         ^~~
joitour.cpp:69:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |         for(int i=0;i<6;i++)dp[i][u].pb(0);id++;
      |                                            ^~

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 8.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33364 KB Output is correct
2 Correct 1045 ms 187216 KB Output is correct
3 Correct 1044 ms 187216 KB Output is correct
4 Correct 1057 ms 187308 KB Output is correct
5 Correct 1047 ms 187220 KB Output is correct
6 Correct 440 ms 178260 KB Output is correct
7 Correct 388 ms 178092 KB Output is correct
8 Correct 811 ms 176024 KB Output is correct
9 Correct 861 ms 178256 KB Output is correct
10 Correct 770 ms 173388 KB Output is correct
11 Correct 761 ms 169808 KB Output is correct
12 Correct 870 ms 184320 KB Output is correct
13 Correct 863 ms 184108 KB Output is correct
14 Correct 827 ms 184144 KB Output is correct
15 Correct 921 ms 184144 KB Output is correct
16 Correct 1071 ms 197964 KB Output is correct
17 Correct 13 ms 33368 KB Output is correct
18 Correct 13 ms 33368 KB Output is correct
19 Correct 13 ms 33668 KB Output is correct
20 Correct 13 ms 33624 KB Output is correct
21 Correct 752 ms 162804 KB Output is correct
22 Correct 730 ms 162780 KB Output is correct
23 Correct 708 ms 163684 KB Output is correct
24 Correct 751 ms 164688 KB Output is correct
25 Correct 111 ms 65660 KB Output is correct
26 Correct 122 ms 65720 KB Output is correct
27 Correct 112 ms 65664 KB Output is correct
28 Correct 114 ms 65684 KB Output is correct
29 Correct 442 ms 197976 KB Output is correct
30 Correct 469 ms 197968 KB Output is correct
31 Correct 426 ms 197968 KB Output is correct
32 Correct 477 ms 197968 KB Output is correct
33 Correct 380 ms 168012 KB Output is correct
34 Correct 424 ms 168228 KB Output is correct
35 Correct 361 ms 168016 KB Output is correct
36 Correct 351 ms 168016 KB Output is correct

Subtask #4
0.0 / 16.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 34.0

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

Subtask #7
0.0 / 14.0

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