Submission #697348

#	Time	Username	Problem	Language	Result	Execution time	Memory
697348		vjudge1	Training (IOI07_training)	C++17	100 / 100	11 ms	4820 KiB

training

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;T f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) print(x/10);
	putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=5007;
int n,m,cnt,h[N],dep[N],pa[N][14],id[N],reid[N],sum,f[N][N];
struct edge{int to,nxt;}mp[N<<1];
struct node{int u,v,w;};
vector<node>edg; vector<int>vct[N];
void add(int x,int y)
{
	cnt++;
	mp[cnt].nxt=h[x];
	mp[cnt].to=y;
	h[x]=cnt;
}
void prework(int x,int fa)
{
	pa[x][0]=fa; dep[x]=dep[fa]+1;
	for(int i=1;i<14;i++)
		pa[x][i]=pa[pa[x][i-1]][i-1];
	for(int i=h[x];i;i=mp[i].nxt)
		if(mp[i].to!=fa)
			prework(mp[i].to,x);
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	int stp=dep[x]-dep[y];
	for(int i=13;i>=0;i--)
		if(stp>=(1<<i))
			stp-=(1<<i),x=pa[x][i];
	if(x==y) return x;
	for(int i=13;i>=0;i--)
		if(pa[x][i]!=pa[y][i])
			x=pa[x][i],y=pa[y][i];
	return pa[x][0];
}
void solve(int x)
{
	int son=0;
	for(int i=h[x];i;i=mp[i].nxt)
	{
		int y=mp[i].to;
		if(y==pa[x][0]) continue;
		solve(y);
	}
	for(int i=h[x];i;i=mp[i].nxt)
	{
		int y=mp[i].to;
		if(y==pa[x][0]) continue;
		id[son]=y; reid[y]=1<<son; son++;
	}
	for(int S=0,now=0;S<(1<<son);S++,now=0)
	{
		for(int i=0;i<son;i++)
			if(!((S>>i)&1))
				now+=f[id[i]][0];
		f[x][S]=now;
	}
	for(int k=vct[x].size()-1;k>=0;k--)
	{
		int i=vct[x][k],now=edg[i].w,a=0,b=0;
		if(edg[i].u!=x) now+=f[edg[i].u][0];
		if(edg[i].v!=x) now+=f[edg[i].v][0];
		if(edg[i].u!=x)
			for(a=edg[i].u;pa[a][0]!=x;a=pa[a][0])
				now+=f[pa[a][0]][reid[a]];
		if(edg[i].v!=x)
			for(b=edg[i].v;pa[b][0]!=x;b=pa[b][0])
				now+=f[pa[b][0]][reid[b]];
		for(int S=0;S<(1<<son);S++)
			if((S&reid[a])==0&&(S&reid[b])==0)
				f[x][S]=max(f[x][S],f[x][S|reid[a]|reid[b]]+now);
	}
}
int main()
{
	read(n,m);
	for(int i=1,x,y,z;i<=m;i++)
	{
		read(x,y,z); sum+=z;
		if(z==0) add(x,y),add(y,x);
		else edg.push_back((node){x,y,z});
	}
	prework(1,0);
	for(int i=0;i<edg.size();i++)
	{
		auto [x,y,z]=edg[i];
		int lca=LCA(x,y);
		if(!((dep[x]+dep[y]-2*dep[lca])&1))
			vct[lca].push_back(i);
	}
	solve(1); print(sum-f[1][0],'\n');
	return 0;
}

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i=0;i<edg.size();i++)
      |              ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9