oj.uz

답안 #698846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
698846 2023-02-14T13:04:41 Z vjudge1 Training (IOI07_training) C++17
100 / 100
 47 ms 24328 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20052 KB Output is correct
2 Correct 8 ms 20052 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 20180 KB Output is correct
2 Correct 9 ms 20308 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 24084 KB Output is correct
2 Correct 18 ms 24232 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20052 KB Output is correct
2 Correct 9 ms 20052 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 20180 KB Output is correct
2 Correct 9 ms 20220 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 20436 KB Output is correct
2 Correct 10 ms 20436 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 21308 KB Output is correct
2 Correct 9 ms 21332 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 22068 KB Output is correct
2 Correct 11 ms 22024 KB Output is correct
3 Correct 15 ms 22100 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 24020 KB Output is correct
2 Correct 47 ms 23872 KB Output is correct
3 Correct 16 ms 23964 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 22020 KB Output is correct
2 Correct 12 ms 22156 KB Output is correct
3 Correct 19 ms 24328 KB Output is correct
4 Correct 14 ms 22072 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23948 KB Output is correct
2 Correct 24 ms 24180 KB Output is correct
3 Correct 36 ms 24160 KB Output is correct
4 Correct 45 ms 24144 KB Output is correct