oj.uz

Submission #417407

# Submission time Handle Problem Language Result Execution time Memory
417407 2021-06-03T16:29:16 Z Nicholas_Patrick Training (IOI07_training) C++17
100 / 100
 178 ms 4604 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4576 KB Output is correct
2 Correct 29 ms 4556 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2380 KB Output is correct
2 Correct 13 ms 2396 KB Output is correct
3 Correct 20 ms 2428 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4448 KB Output is correct
2 Correct 56 ms 4428 KB Output is correct
3 Correct 43 ms 4496 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2380 KB Output is correct
2 Correct 22 ms 2380 KB Output is correct
3 Correct 71 ms 4556 KB Output is correct
4 Correct 19 ms 2380 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 4540 KB Output is correct
2 Correct 22 ms 4604 KB Output is correct
3 Correct 178 ms 4568 KB Output is correct
4 Correct 72 ms 4408 KB Output is correct