# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
1038716 |
2024-07-30T06:43:45 Z |
정희우(#10988) |
JOI tour (JOI24_joitour) |
C++17 |
|
1144 ms |
322640 KB |
#include "joitour.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;
const int MAX_N=200010;
const int BN=20;
struct Seg
{
int c[3];
};
struct Dat
{
lint c0,c01,c2,c21,c02;
void operator += (const Dat &d)
{
c0+=d.c0;c01+=d.c01;c2+=d.c2;c21+=d.c21;c02+=d.c02;
}
};
struct Obj
{
Dat d;
int segsz;
vector<Seg> seg;
void update_(int i,int s,int e,int l,int r,int v,int k,int c1)
{
if(s>=r || e<=l)return;
if(l<=s && e<=r)
{
seg[i].c[v]+=k;
if(v==0)
{
d.c0+=k;
d.c01+=k*c1;
}
if(v==1)
{
d.c01+=k*seg[i].c[0];
d.c21+=k*seg[i].c[2];
}
if(v==2)
{
d.c2+=k;
d.c21+=k*c1;
}
return;
}
c1+=seg[i].c[1];
update_(i<<1,s,(s+e)>>1,l,r,v,k,c1);
update_(i<<1|1,(s+e)>>1,e,l,r,v,k,c1);
for(int t=0;t<3;t+=2)
seg[i].c[t]=seg[i<<1].c[t]+seg[i<<1|1].c[t];
}
};
int n;
int col[MAX_N];
vint edge[MAX_N];
int sz[MAX_N];
int lock[MAX_N];
int cp[MAX_N],cd[MAX_N];
int sub[MAX_N][BN],si[MAX_N][BN],ei[MAX_N][BN];
Dat based[MAX_N];
vector<Obj> subd[MAX_N];
lint ans=0;
int fillsz(int v,int p)
{
sz[v]=1;
for(auto v0 : edge[v])
if(v0!=p && lock[v0]==0)
sz[v]+=fillsz(v0,v);
return sz[v];
}
int findc(int v,int p,int h)
{
for(auto v0 : edge[v])
if(v0!=p && lock[v0]==0 && sz[v0]>h)
return findc(v0,v,h);
return v;
}
void dfs(int v,int p,int d,int i1,int &i2)
{
sub[v][d]=i1;
si[v][d]=i2++;
for(auto v0 : edge[v])
if(v0!=p && lock[v0]==0)
dfs(v0,v,d,i1,i2);
ei[v][d]=i2;
}
void upd(int v,int d,int c,int k)
{
if(col[v]==1)
subd[c][sub[v][d]].update_(1,0,subd[c][sub[v][d]].segsz,si[v][d],ei[v][d],col[v],k,0);
else
subd[c][sub[v][d]].update_(1,0,subd[c][sub[v][d]].segsz,si[v][d],si[v][d]+1,col[v],k,0);
}
void updall(int v,int p,int d,int c)
{
upd(v,d,c,1);
for(auto v0 : edge[v])
if(v0!=p && lock[v0]==0)
updall(v0,v,d,c);
}
void updcent(int v,int k)
{
if(col[v]==0)
ans+=k*based[v].c21;
if(col[v]==1)
ans+=k*(based[v].c0*based[v].c2-based[v].c02);
if(col[v]==2)
ans+=k*based[v].c01;
}
void f(int v,int c,int d)
{
fillsz(v,v);
int cent=findc(v,v,sz[v]/2);
cp[cent]=c;
cd[cent]=d;
int idx1=0,idx2=0;
for(auto v0 : edge[cent])
if(lock[v0]==0)
dfs(v0,cent,d,idx1++,idx2);
subd[cent].resize(idx1);
idx1=0;
for(auto v0 : edge[cent])
if(lock[v0]==0)
{
subd[cent][idx1].segsz=ei[v0][d];
subd[cent][idx1].seg.resize(ei[v0][d]<<2);
updall(v0,cent,d,cent);
Dat d=subd[cent][idx1].d;
based[cent]+=d;
based[cent].c02+=d.c0*d.c2;
ans-=d.c0*d.c21+d.c2*d.c01;
idx1++;
}
ans+=based[cent].c0*based[cent].c21+based[cent].c2*based[cent].c01;
updcent(cent,1);
lock[cent]=1;
for(auto v0 : edge[cent])
if(lock[v0]==0)
f(v0,cent,d+1);
}
void init(int N, vint F, vint U, vint V, int Q)
{
n=N;
for(int i=0;i<n;i++)col[i]=F[i];
for(int i=0;i<n-1;i++)
{
int u=U[i],v=V[i];
edge[u].push_back(v);
edge[v].push_back(u);
}
f(0,-1,0);
}
void change(int X, int Y)
{
}
long long num_tours()
{
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Incorrect |
2 ms |
14772 KB |
Wrong Answer [1] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Incorrect |
2 ms |
14772 KB |
Wrong Answer [1] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
14936 KB |
Output is correct |
2 |
Correct |
1077 ms |
322232 KB |
Output is correct |
3 |
Correct |
1144 ms |
322040 KB |
Output is correct |
4 |
Correct |
1101 ms |
320004 KB |
Output is correct |
5 |
Correct |
1127 ms |
322640 KB |
Output is correct |
6 |
Incorrect |
561 ms |
305584 KB |
Wrong Answer [1] |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
14936 KB |
Output is correct |
2 |
Incorrect |
2 ms |
14936 KB |
Wrong Answer [1] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
14936 KB |
Wrong Answer [1] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Incorrect |
2 ms |
14772 KB |
Wrong Answer [1] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Incorrect |
2 ms |
14772 KB |
Wrong Answer [1] |
3 |
Halted |
0 ms |
0 KB |
- |