oj.uz

Submission #1038703

# Submission time Handle Problem Language Result Execution time Memory
1038703 2024-07-30T06:32:59 Z 정희우(#10988) JOI tour (JOI24_joitour) C++17
0 / 100
 1345 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>;
using vlint = vector<lint>;

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<2;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;
}

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 1345 ms 322196 KB Output is correct
3 Correct 1240 ms 321864 KB Output is correct
4 Correct 1198 ms 320080 KB Output is correct
5 Correct 1209 ms 322640 KB Output is correct
6 Incorrect 557 ms 305744 KB Wrong Answer [1]
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 16.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 34.0

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

Subtask #7
0.0 / 14.0

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