Submission #698846

#	Time	Username	Problem	Language	Result	Execution time	Memory
698846		vjudge1	Training (IOI07_training)	C++17	100 / 100	47 ms	24328 KiB

training

#include<bits/stdc++.h>
#define y1 y3647
#define INF 1000000000
#define LL long long
#define pii pair<int,int>
using namespace std;
long long read(){
	long long x=0;int f=1;char ch=getchar();
	while(ch!=45&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch==45){f=-1,ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*=f;
}
template<typename T>T&read(T&x){return x=read();}
template<typename T,typename W>T&cmin(T&a,const W&b){return a>b?(a=b):a;}
template<typename T,typename W>T&cmax(T&a,const W&b){return a<b?(a=b):a;}
const int N=1005,M=5005;
int n,m,t,sum;
int dp[N][M],a[M][3],fa[N],dis[N],vis[N],mp[N][N],dep[N],ed[M][2];
vector<int> e[N],b[N],c[N];
void dfs(int u){
	sort(e[u].begin(),e[u].end());
	for(auto v:e[u]){
		if(fa[u]==v)continue;
		fa[v]=u;dis[v]=dis[u]^1;dep[v]=dep[u]+1;
		dfs(v);
	}
}
pair<int,int> lca(int u,int v){
	if(dep[v]>dep[u])swap(u,v);
	while(dep[u]!=dep[v]&&fa[u]!=v)u=fa[u];
	if(fa[u]==v)return make_pair(u,v);
	while(fa[u]!=fa[v])u=fa[u],v=fa[v];
	return make_pair(u,v);
}
int _lca(int u,int v){
	if(dep[u]==dep[v])return fa[u];
	return dep[u]>dep[v]?v:u;
}
void DFS(int now,vector<int> &a,int rt){
	if(now==a.size()){
		int tot=0;
		for(auto v:a){
			if(vis[v]==n+1)tot+=mp[rt][v];			
			else if(v<vis[v])tot+=mp[v][vis[v]];
		}
		cmax(sum,tot);
		return ;
	}
	if(vis[a[now]])return DFS(now+1,a,rt);
	for(int i=now+1;i<a.size();i++)if(!vis[a[i]]){
		vis[a[now]]=a[i],vis[a[i]]=a[now];
		DFS(now+1,a,rt);
		vis[a[now]]=vis[a[i]]=0;
	}
	vis[a[now]]=n+1;
	DFS(now+1,a,rt);
	vis[a[now]]=0;
}
int solve_basic(vector<int> a,int u){
	sum=0;
	DFS(0,a,u);
	return sum;
}
void solve(int u){
//	for(auto w:e[u])printf("%d ",w);puts("");
	if(u!=1)e[u].erase(lower_bound(e[u].begin(),e[u].end(),fa[u]));
	for(auto v:e[u])
	solve(v),mp[u][v]=mp[v][u]=dp[v][0];	
	for(auto w:c[u]){
		int s1=ed[w][0],s2=ed[w][1];
		cmax(mp[s1][s2],(s1!=u?dp[s1][w]:0)+(s2!=u?dp[s2][w]:0)+a[w][2]);
		mp[s2][s1]=mp[s1][s2];
	}
	dp[u][0]=solve_basic(e[u],u);
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];auto tp=e[u];
		tp.erase(lower_bound(tp.begin(),tp.end(),v));
		int val=solve_basic(tp,u);	
		for(int j=1;j<=m;j++)if(~dp[v][j])dp[u][j]=val+dp[v][j];
	}
	for(auto v:b[u])dp[u][v]=dp[u][0];
}
void ___solve(){
	int i,j,ans=0;
	read(n),read(m);
	for(i=1;i<=m;i++){
		read(a[i][0]),read(a[i][1]),read(a[i][2]);
		if(a[i][2]==0)e[a[i][0]].push_back(a[i][1]),e[a[i][1]].push_back(a[i][0]);
	}
	dfs(1);
	for(i=1;i<=m;i++){
		if(a[i][2]==0)continue;
		if(dis[a[i][0]]^dis[a[i][1]]==0){
			tie(ed[i][0],ed[i][1])=lca(a[i][1],a[i][0]);
			b[a[i][0]].push_back(i);
			b[a[i][1]].push_back(i);
			c[_lca(ed[i][0],ed[i][1])].push_back(i);
		}
		ans+=a[i][2];
	}
	memset(dp,-1,sizeof(dp));
	solve(1);
	cout<<ans-dp[1][0]<<endl;
}
signed main()
{
// 	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	freopen(".in","w",stdout);
	int tot=1;
//	read(tot);
	while(tot--){
		___solve();
	}
	return 0;
}

Compilation message (stderr)

training.cpp: In function 'void DFS(int, std::vector<int>&, int)':
training.cpp:40:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  if(now==a.size()){
      |     ~~~^~~~~~~~~~
training.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=now+1;i<a.size();i++)if(!vis[a[i]]){
      |                  ~^~~~~~~~~
training.cpp: In function 'void solve(int)':
training.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0;i<e[u].size();i++){
      |              ~^~~~~~~~~~~~
training.cpp: In function 'void ___solve()':
training.cpp:93:31: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   93 |   if(dis[a[i][0]]^dis[a[i][1]]==0){
      |                   ~~~~~~~~~~~~^~~
training.cpp:84:8: warning: unused variable 'j' [-Wunused-variable]
   84 |  int i,j,ans=0;
      |        ^

• 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