oj.uz

Submission #697270

# Submission time Handle Problem Language Result Execution time Memory
697270 2023-02-09T02:50:47 Z vjudge1 Training (IOI07_training) C++14
100 / 100
 13 ms 4644 KB 
#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
using namespace std;
namespace IO
{
	const int SZ=1<<20;
	char gchar()
	{
	    static char buf[SZ];
	    static int i=SZ;
	    if(i==SZ)i=0,fread(buf,1,SZ,stdin);
	    return buf[i++];
	}
	void pchar(char c)
	{
	    static char buf[SZ];
	    static int i=0;
	    if(c)buf[i++]=c;
	    if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
	}
	void pstr(string s,char end='\n')
	{
		for(char c:s)pchar(c);
		pchar(end);
	}
	template<typename T>void read(T &x)
	{
	    x=0;int f=1;
	    static char c;
	    while((c=gchar())>'9'||c<'0')if(c=='-')f=-1;
	    x=c-'0';
	    while((c=gchar())>='0'&&c<='9')
			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 i_write(T x)
	{
	    if(x>9)i_write(x/10);
	    pchar(x%10+'0');
	}
	template<typename T>void write(T x,char end='\n')
	{
	    if(x<0)pchar('-'),x=-x;
	    if(x>9)i_write(x/10);
	    pchar(x%10+'0');
	    pchar(end);
	}
}
using IO::read;
using IO::write;
const int N=1010;
int n,m,ans;
vector<int>e[N];
struct node
{
	int src,des,val;
};
vector<node>vec,link[N];
int dep[N],fa[N],siz[N],wson[N],top[N],fid[N];
int f[N][1<<10];
void dfs1(int u,int f)
{
	fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
	for(int v:e[u])
	{
		if(v==f)continue;
		dfs1(v,u),siz[u]+=siz[v];
		if(siz[v]>siz[wson[u]])wson[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	if(wson[u])dfs2(wson[u],t);
	for(int v:e[u])
		if(v!=wson[u]&&v!=fa[u])dfs2(v,v);
}
void dfs3(int u)
{
	for(int i=0;i<(int)e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa[u])continue;
		fid[v]=1<<i,dfs3(v);
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]>dep[v]?v:u;
}
void dfs(int u)
{
	for(int v:e[u])
		if(v!=fa[u])dfs(v);
	int cnt=e[u].size();
	for(int msk=0;msk<(1<<cnt);msk++)
		for(int i=0;i<cnt;i++)
			if(!(msk&(1<<i)))f[u][msk]+=f[e[u][i]][0];
	for(auto e:link[u])
	{
		int val=e.val,x=0,y=0;
		if(e.src!=u)
		{
			val+=f[e.src][0];
			for(x=e.src;fa[x]!=u;x=fa[x])
				val+=f[fa[x]][fid[x]];
		}
		if(e.des!=u)
		{
			val+=f[e.des][0];
			for(y=e.des;fa[y]!=u;y=fa[y])
				val+=f[fa[y]][fid[y]];
		}
		int s=fid[x]|fid[y];
		for(int msk=0;msk<(1<<cnt);msk++)
			if(!(msk&s))f[u][msk]=max(f[u][msk],val+f[u][msk|s]);
	}
}
int main()
{
	read(n,m);
	for(int i=1,u,v,w;i<=m;i++)
	{
		read(u,v,w);
		if(!w)e[u].push_back(v),e[v].push_back(u);
		else ans+=w,vec.push_back((node){u,v,w});
	}
	dfs1(1,0),dfs2(1,1),dfs3(1);
	for(auto e:vec)
	{
		int x=lca(e.src,e.des);
		if(!((dep[e.src]+dep[e.des]-dep[x]*2)&1))
			link[x].push_back(e);
	}
	dfs(1);
	printf("%d",ans-f[1][0]);
	return 0;
}

Compilation message

training.cpp: In function 'char IO::gchar()':
training.cpp:18:24: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |      if(i==SZ)i=0,fread(buf,1,SZ,stdin);
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 488 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4488 KB Output is correct
2 Correct 5 ms 4620 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 368 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 488 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1528 KB Output is correct
2 Correct 1 ms 1652 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2440 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 4 ms 2388 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 6 ms 4564 KB Output is correct
3 Correct 3 ms 4564 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 13 ms 4616 KB Output is correct
4 Correct 4 ms 2440 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4564 KB Output is correct
2 Correct 11 ms 4644 KB Output is correct
3 Correct 6 ms 4636 KB Output is correct
4 Correct 8 ms 4644 KB Output is correct