Submission #575143

#	Time	Username	Problem	Language	Result	Execution time	Memory
575143		Antekb	Training (IOI07_training)	C++14	17 / 100	2 ms	468 KiB

training

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=20;
int vis[N];
vector<int> E[N];
vector<pair<int, int> > edg;
vector<int> wei;
int n, m;
int ans=1e9, cur;
int go(int v, int p){
	for(int u:E[v]){
		if(u!=p && vis[u])if((vis[v]+vis[u])&1)return 0;
		if(!vis[u]){
			//cout<<u<<"\n";
			vis[u]=vis[v]+1;
			if(!go(u, v))return 0;
			//cout<<u<<"\n";
			vis[u]=0;
		}
	}
	return 1;
}
void solve(int i){
	if(i==edg.size()){
		if(go(1, 0)){
			ans=min(ans, cur);
		}
		for(int i=2; i<=n; i++)vis[i]=0;
		return;
	}
	E[edg[i].st].push_back(edg[i].nd);
	E[edg[i].nd].push_back(edg[i].st);
	solve(i+1);
	E[edg[i].st].pop_back();
	E[edg[i].nd].pop_back();
	cur+=wei[i];
	solve(i+1);
	cur-=wei[i];
}
int main(){
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int u, v, w;
		cin>>u>>v>>w;
		if(w==0){
			E[u].push_back(v);
			E[v].push_back(u);
		}
		else{
			edg.push_back({u, v});
			wei.push_back(w);
		}
	}
	vis[1]=1;
	solve(0);
	cout<<ans;
}

Compilation message (stderr)

training.cpp: In function 'void solve(int)':
training.cpp:26:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if(i==edg.size()){
      |     ~^~~~~~~~~~~~

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