Submission #417407

#	Time	Username	Problem	Language	Result	Execution time	Memory
417407		Nicholas_Patrick	Training (IOI07_training)	C++17	100 / 100	178 ms	4604 KiB

training

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn=1000;
const int maxd=10;
struct bare{
	int a, b, c;
};
vector<int> adjlis[maxn];
int root;
int depth[maxn];
int parent[maxn];
int fap[maxn], sap[maxn];
int et;
void dfs1(int x=root){
	fap[x]=et++;
	for(int y : adjlis[x]){
		adjlis[y].erase(find(adjlis[y].begin(), adjlis[y].end(), x));
		depth[y]=depth[x]+1;
		parent[y]=x;
		dfs1(y);
	}
	sap[x]=et;
}
int lca(int x, int y){
	if(depth[x]>depth[y])
		swap(x, y);
	while(depth[x]<depth[y])
		y=parent[y];
	while(x!=y)
		x=parent[x], y=parent[y];
	return x;
}
vector<bare> paths[maxn];
const int uncalculated=-1000000000;
int memo[maxn][maxn];
int memo2[maxn][maxd];
int dfs2(int x=root, int bad=root){
	int& ret=memo[x][bad];
	if(ret!=uncalculated)
		return ret;
	if(x==bad){
		int sz=1<<adjlis[x].size();
		int dp[sz];
		fill(dp, dp+sz, 0);
		for(const auto& i : paths[x]){
			int rec=i.c;
			int index=0;
			if(i.a!=x){
				for(int j=0; j<adjlis[x].size(); j++){
					if(fap[adjlis[x][j]]<=fap[i.a] and sap[i.a]<=sap[adjlis[x][j]]){
						index|=1<<j;
						rec+=dfs2(adjlis[x][j], i.a)-dfs2(adjlis[x][j], adjlis[x][j]);
						break;
					}
				}
			}
			if(i.b!=x){
				for(int j=0; j<adjlis[x].size(); j++){
					if(fap[adjlis[x][j]]<=fap[i.b] and sap[i.b]<=sap[adjlis[x][j]]){
						index|=1<<j;
						rec+=dfs2(adjlis[x][j], i.b)-dfs2(adjlis[x][j], adjlis[x][j]);
						break;
					}
				}
			}
			dp[index]=max(dp[index], rec);
		}
		for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
			dp[k]=max(dp[k], dp[i]+dp[k^i]);
		ret=dp[sz-1];
		for(int y : adjlis[x])
			ret+=dfs2(y, y);
		return ret;
	}else{
		int banned;
		for(int i=0; i<adjlis[x].size(); i++){
			if(fap[adjlis[x][i]]<=fap[bad] and sap[bad]<=sap[adjlis[x][i]]){
				banned=i;
				break;
			}
		}
		int sz=1<<adjlis[x].size();
		int dp[sz];
		fill(dp, dp+sz, 0);
		for(const auto& i : paths[x]){
			int rec=i.c;
			int index=0;
			if(i.a!=x){
				for(int j=0; j<adjlis[x].size(); j++){
					if(fap[adjlis[x][j]]<=fap[i.a] and sap[i.a]<=sap[adjlis[x][j]]){
						index|=1<<j;
						rec+=dfs2(adjlis[x][j], i.a)-dfs2(adjlis[x][j], adjlis[x][j]);
						break;
					}
				}
			}
			if(i.b!=x){
				for(int j=0; j<adjlis[x].size(); j++){
					if(fap[adjlis[x][j]]<=fap[i.b] and sap[i.b]<=sap[adjlis[x][j]]){
						index|=1<<j;
						rec+=dfs2(adjlis[x][j], i.b)-dfs2(adjlis[x][j], adjlis[x][j]);
						break;
					}
				}
			}
			if(index>>banned&1)
				continue;
			dp[index]=max(dp[index], rec);
		}
		for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
			dp[k]=max(dp[k], dp[i]+dp[k^i]);
		ret=dp[sz-1];
		for(int i=0; i<adjlis[x].size(); i++){
			if(i==banned){
				ret+=dfs2(adjlis[x][i], bad);
			}else{
				ret+=dfs2(adjlis[x][i], adjlis[x][i]);
			}
		}
		return ret;
	}
}
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	vector<bare> bares;
	for(int i=m; i--;){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c), a--, b--;
		if(c){
			bares.push_back(bare{a, b, c});
		}else{
			adjlis[a].push_back(b);
			adjlis[b].push_back(a);
		}
	}
	for(int i=n; i--;){
		if(adjlis[i].size()==1)
			root=i;
	}
	depth[root]=0;
	et=0;
	dfs1();
	int ans=0;
	for(auto& i : bares){
		ans+=i.c;
		if(~(depth[i.a]+depth[i.b])&1)
			paths[lca(i.a, i.b)].push_back(i);
	}
	for(int i=0; i<n; i++){
		fill(memo[i], memo[i]+n, uncalculated);
		fill(memo2[i], memo2[i]+maxd, uncalculated);
	}
	printf("%d\n", ans-dfs2());
}

Compilation message (stderr)

training.cpp: In function 'int dfs2(int, int)':
training.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int j=0; j<adjlis[x].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~~
training.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int j=0; j<adjlis[x].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~~
training.cpp:71:49: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   71 |   for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
      |                                                ~^~
training.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=0; i<adjlis[x].size(); i++){
      |                ~^~~~~~~~~~~~~~~~~
training.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int j=0; j<adjlis[x].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~~
training.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int j=0; j<adjlis[x].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~~
training.cpp:113:49: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  113 |   for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
      |                                                ~^~
training.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |   for(int i=0; i<adjlis[x].size(); i++){
      |                ~^~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
training.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d%d%d", &a, &b, &c), a--, b--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
training.cpp: In function 'int dfs2(int, int)':
training.cpp:78:7: warning: 'banned' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |   int banned;
      |       ^~~~~~

• 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