Submission #1202309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202309		8pete8	JOI tour (JOI24_joitour)	C++20	16 / 100	364 ms	238620 KiB

joitour

#include "joitour.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse,sse2,sse3")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=31,Mxn=6e6,base=131;
//#undef int
int n,k,m,q,L,T;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int F[mxn+10];
vector<int>adj[mxn+10];
enum Type{Vertex,Compress,Rake,AddEdge,AddVertex};
struct sttree{
	int root,stroot;
	vector<int>P,L,R;
	vector<Type>T;
	int ct;
  void init(int x){
    root=x;
    build();
  }
	private:
	int gethvy(int cur,int p){
		int best=0,sz=1;
		for(auto &i:adj[cur])if(i!=p){
			int x=gethvy(i,cur);
			sz+=x;
			if(x>best)best=x,swap(adj[cur][0],i);
		}
    //if(adj[cur].size())cout<<cur<<" "<<adj[cur][0]<<"?\n";
		return sz;
	}
	int add(int k,int l,int r,Type t){
		if(k==-1)k=++ct;
		L[k]=l,R[k]=r,T[k]=t;
		if(l!=-1)P[l]=k;
		if(r!=-1)P[r]=k;
		return k;
	}
	pii merge(vector<pii>have,Type t){
		if(have.size()==1)return have[0];
		int cs=0;
		for(auto i:have)cs+=i.s;
		vector<pii>a,b;
		for(auto i:have){
			if(i.s<cs)a.pb(i);
			else b.pb(i);
			cs-=2*i.s;
		}
		pii x=merge(a,t),y=merge(b,t);
		return {add(-1,x.f,y.f,t),x.s+y.s};
	}
	pii compress(int cur){
		vector<pii>have={addvertex(cur)};
		while(adj[cur].size())cur=adj[cur][0],have.pb(addvertex(cur));
		return merge(have,Type::Compress);
	}
	pii rake(int cur){
		vector<pii>have;
		for(int i=1;i<adj[cur].size();i++)have.pb(addedge(adj[cur][i]));
		return have.empty()? (pii){-1,0} : merge(have,Type::Rake);
	}
	pii addedge(int cur){
		pii x=compress(cur);
		return {add(-1,x.f,-1,Type::AddEdge),x.s};
	}
	pii addvertex(int cur){
		pii x=rake(cur);
		return {add(cur,x.f,-1,(x.f==-1)?Type::Vertex : Type::AddVertex),x.s+1};
	}
	void build(){
		P.resize(4*n+1,-1),L.resize(4*n+1,-1),R.resize(4*n+1,-1);
		T.resize(4*n+1);
		ct=n;
		gethvy(root,-1);
		stroot=compress(root).f;
	}
};
struct path{
	int dp[3][3],ca=0;
	int c[3];//cnt 1
	path(){
		for(int i=0;i<3;i++){
      c[i]=0;
      for(int j=0;j<3;j++)dp[i][j]=0;
    }
	}
};
struct point{
	int dp[3][3],ca=0,ca2=0;
	point(){for(int i=0;i<3;i++)for(int j=0;j<3;j++)dp[i][j]=0;}
};
path vertex(int i){
	path x;
	x.dp[F[i]][F[i]]++;
	return x;
}
path compress(path a,path b){
	path x;
	x.ca+=a.ca+b.ca;
  x.dp[0][1]=a.dp[0][0]*b.dp[1][1];
  x.dp[0][2]=(a.dp[0][0]*b.dp[1][2])+(a.dp[0][1]*b.dp[2][2]);
  x.dp[1][0]=(a.dp[1][1]*b.dp[0][0]);
  x.dp[1][2]=(a.dp[1][1]*b.dp[2][2]);
  x.dp[2][1]=a.dp[2][2]*b.dp[1][1];
  x.dp[2][0]=(a.dp[2][2]*b.dp[1][0])+(a.dp[2][1]*b.dp[0][0]);
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)x.dp[i][j]+=a.dp[i][j]+b.dp[i][j];
	return x;
}
point rake(point a,point b){
	point x;
	x.ca+=(a.dp[0][0]*b.dp[1][2])+(a.dp[1][0]*b.dp[2][2])+(a.dp[2][2]*b.dp[1][0])+(a.dp[1][2]*b.dp[0][0]);
	x.ca+=a.ca+b.ca;
	x.ca2=a.ca2+b.ca2+(a.dp[0][0]*b.dp[2][2])+(a.dp[2][2]*b.dp[0][0]);
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)x.dp[i][j]=a.dp[i][j]+b.dp[i][j];
	return x;
}
path addvertex(point a,int i){
	path x;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++)if(i==j||i==1)x.dp[i][j]=a.dp[i][j];
  }
	x.ca=a.ca;
	if(F[i]==0){
		x.ca+=a.dp[1][2];
		x.dp[0][0]++;
	}
	else if(F[i]==2){
		x.ca+=a.dp[1][0];
		x.dp[2][2]++;
	}
	else{
		x.ca+=a.ca2;
		x.dp[1][2]+=x.dp[2][2];
		x.dp[1][0]+=x.dp[0][0];
		x.dp[1][1]++;
	}
	return x;
}
point addedge(path a){
	point x;
	x.ca=a.ca+a.dp[2][0]+a.dp[0][2];
  for(int i=0;i<3;i++)for(int j=0;j<3;j++)x.dp[i][j]=a.dp[i][j];
	return x;
}
vector<path>Path;
vector<point>Point;
sttree stt;
void update(int cur){
  if(stt.T[cur]==Type::Vertex){
    Path[cur]=vertex(cur);
  }
  if(stt.T[cur]==Type::Compress){
    Path[cur]=compress(Path[stt.L[cur]],Path[stt.R[cur]]);
  }
  if(stt.T[cur]==Type::Rake){
    Point[cur]=rake(Point[stt.L[cur]],Point[stt.R[cur]]);
  }
  if(stt.T[cur]==Type::AddEdge){
    Point[cur]=addedge(Path[stt.L[cur]]);
  }
  if(stt.T[cur]==Type::AddVertex){
    Path[cur]=addvertex(Point[stt.L[cur]],cur);
  }
}
void dfs(int cur){
  if(cur==-1)return;
  dfs(stt.L[cur]);
  dfs(stt.R[cur]);
  //cout<<cur<<" "<<stt.L[cur]<<" "<<stt.R[cur]<<"K\n";
  update(cur);
}
vector<int>adj2[mxn+10];
void getadj(int cur,int p){
  for(auto i:adj2[cur])if(i!=p){
    adj[cur].pb(i);
    getadj(i,cur);
  }
}
void init(int32_t N, std::vector<int32_t> FF, std::vector<int32_t> U, std::vector<int32_t> V,int32_t Q) {
  n=N;
  for(int i=0;i<n-1;i++)adj2[U[i]].pb(V[i]),adj2[V[i]].pb(U[i]);
  getadj(0,-1);
  for(int i=0;i<n;i++)F[i]=FF[i];
  Path.resize(4*n+1);
  Point.resize(4*n+1);
  stt.init(0);
  dfs(stt.stroot);
}
void change(int32_t x, int32_t y){
  F[x]=y;
  while(x!=-1){
    update(x);
    x=stt.P[x];
  }
}
long long num_tours(){
  return Path[stt.stroot].ca+Path[stt.stroot].dp[2][0]+Path[stt.stroot].dp[0][2];
}
/*

*/

Compilation message (stderr)

joitour.cpp: In function 'void setIO(std::string)':
joitour.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joitour.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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