oj.uz

Submission #77683

# Submission time Handle Problem Language Result Execution time Memory
77683 2018-09-29T18:16:34 Z updown1 Chase (CEOI17_chase) C++17
100 / 100
 1322 ms 521092 KB 
#include<bits/stdc++.h>
using namespace std;
#define For(i, a, b) for (int i=a; i<b; i++)
#define ffi For (i, 0, N)
#define ffj For (j, 0, V+1)
#define ffa ffi ffj
#define w cout
#define e "\n"
#define s <<" "<<
#define pb push_back
#define a first
#define b second
#define mp make_pair

const int MAXN = 100000, MAXV = 101;
int N, V, p[MAXN];
long long nei[MAXN], out;
bool visited[MAXN];
vector<int> inp[MAXN], adj[MAXN];
long long dp1[MAXN][MAXV][3], dp2[MAXN][MAXV][3];



void get1(int at, int b) {
	if (b < 0 || dp1[at][b][2] != -1) return;
	
	dp1[at][b][0] = dp1[at][b][2] = 0;
	dp1[at][b][1] = -2;
	
	For (i, 0, adj[at].size()) {
		int x = adj[at][i];
		//get1(x, b), get1(x, b-1);
		
		bool worked = false;
		//Don't put crumb at x
		if (dp1[x][b][0] > dp1[at][b][0]) {
			dp1[at][b][2] = dp1[at][b][0];
			dp1[at][b][0] = dp1[x][b][0];
			dp1[at][b][1] = x;
			worked = true;
		}
		else if (dp1[x][b][0] > dp1[at][b][2]) {
			dp1[at][b][2] = dp1[x][b][0];
		}
		
		//Put crumb at x
		if (b != 0) {
			long long y = dp1[x][b-1][0] + nei[x] - p[at];
			if (y > dp1[at][b][0]) {
				if (!worked) dp1[at][b][2] = dp1[at][b][0];
				dp1[at][b][0] = y;
				dp1[at][b][1] = x;
			}
			else if (y > dp1[at][b][2] && !worked) {
				dp1[at][b][2] = y;
			}
		}
	}
}

void get2 (int at, int b) {
	if (b < 0 || dp2[at][b][2] != -1) return;
	
	dp2[at][b][0] = dp2[at][b][2] = 0;
	dp2[at][b][1] = -2;
	if (b > 0) dp2[at][b][0] = nei[at]; 
	
	For (i, 0, adj[at].size()) {
		int x = adj[at][i];
		//get2(x, b), get2(x, b-1);
		
		bool worked = false;
		//Don't put crumb on at
		if (dp2[x][b][0] > dp2[at][b][0]) {
			dp2[at][b][2] = dp2[at][b][0];
			dp2[at][b][0] = dp2[x][b][0];
			dp2[at][b][1] = x;
			worked = true;
		}
		else if (dp2[x][b][0] > dp2[at][b][2]) {
			dp2[at][b][2] = dp2[x][b][0];
		}
		
		//Put crumb on at
		if (b != 0) {
			long long y = dp2[x][b-1][0] + nei[at] - p[x];
			if (y > dp2[at][b][0]) {
				if (!worked) dp2[at][b][2] = dp2[at][b][0];
				dp2[at][b][0] = y;
				dp2[at][b][1] = x;
			}
			else if (y > dp2[at][b][2] && !worked) {
				dp2[at][b][2] = y;
			}
		}
	}
}

void go(int at) {
	visited[at] = true;
	For (i, 0, inp[at].size()) if (!visited[inp[at][i]]) {
		adj[at].pb(inp[at][i]);
		go(inp[at][i]);
	}
	ffj get1(at, j), get2(at, j);
}


int main () {
	//ifstream cin("chase.04.01.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> V;
	ffi cin >> p[i];
	For (i, 1, N) {
		int a, b; cin >> a >> b; a--; b--; inp[a].pb(b); inp[b].pb(a);
	}
	ffi {
		For (j, 0, inp[i].size()) nei[i] += p[inp[i][j]];
		ffj For (k, 0, 3) dp1[i][j][k] = dp2[i][j][k] = -1;
	}
	go(0);
	//ffi w<< nei[i]<<e;
	ffi {
		ffj {
			//get1(i, j);
			//w<< "one" s i+1 s j s ":" s dp1[i][j].a.a s "from" s dp1[i][j].a.b+1 s "," s dp1[i][j].b<<e;
			//get2(i, V-j);
			//w<< i+1 s V-j s ":" s dp2[i][V-j].a.a s "from" s dp2[i][V-j].a.b+1 s "," s dp2[i][V-j].b<<e;
			if (dp1[i][j][1] == dp2[i][V-j][1]) {
				out = max(out, max(dp1[i][j][0] + dp2[i][V-j][2], dp1[i][j][2] + dp2[i][V-j][0]));
				if ( max(dp1[i][j][0] + dp2[i][V-j][2], dp1[i][j][2] + dp2[i][V-j][0]) == 37) {
					//w<< "DSADSAASD" s i+1 s j s V-j<<e;
				}
			}
			else out = max(out, dp1[i][j][0] + dp2[i][V-j][0]);
		}
	}
	w<< out<<e;
}

Compilation message

chase.cpp: In function 'void get1(int, int)':
chase.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for (int i=a; i<b; i++)
chase.cpp:30:7:
  For (i, 0, adj[at].size()) {
       ~~~~~~~~~~~~~~~~~~~~           
chase.cpp:30:2: note: in expansion of macro 'For'
  For (i, 0, adj[at].size()) {
  ^~~
chase.cpp: In function 'void get2(int, int)':
chase.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for (int i=a; i<b; i++)
chase.cpp:68:7:
  For (i, 0, adj[at].size()) {
       ~~~~~~~~~~~~~~~~~~~~           
chase.cpp:68:2: note: in expansion of macro 'For'
  For (i, 0, adj[at].size()) {
  ^~~
chase.cpp: In function 'void go(int)':
chase.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for (int i=a; i<b; i++)
chase.cpp:101:7:
  For (i, 0, inp[at].size()) if (!visited[inp[at][i]]) {
       ~~~~~~~~~~~~~~~~~~~~           
chase.cpp:101:2: note: in expansion of macro 'For'
  For (i, 0, inp[at].size()) if (!visited[inp[at][i]]) {
  ^~~
chase.cpp: In function 'int main()':
chase.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for (int i=a; i<b; i++)
chase.cpp:118:8:
   For (j, 0, inp[i].size()) nei[i] += p[inp[i][j]];
        ~~~~~~~~~~~~~~~~~~~           
chase.cpp:118:3: note: in expansion of macro 'For'
   For (j, 0, inp[i].size()) nei[i] += p[inp[i][j]];
   ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 6 ms 5296 KB Output is correct
6 Correct 6 ms 5296 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 6 ms 5296 KB Output is correct
6 Correct 6 ms 5296 KB Output is correct
7 Correct 15 ms 10132 KB Output is correct
8 Correct 10 ms 10132 KB Output is correct
9 Correct 10 ms 10132 KB Output is correct
10 Correct 14 ms 10264 KB Output is correct
11 Correct 11 ms 10300 KB Output is correct
12 Correct 10 ms 10452 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 492028 KB Output is correct
2 Correct 830 ms 494124 KB Output is correct
3 Correct 1321 ms 494124 KB Output is correct
4 Correct 467 ms 494496 KB Output is correct
5 Correct 870 ms 496456 KB Output is correct
6 Correct 885 ms 498684 KB Output is correct
7 Correct 934 ms 500856 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 6 ms 5296 KB Output is correct
6 Correct 6 ms 5296 KB Output is correct
7 Correct 15 ms 10132 KB Output is correct
8 Correct 10 ms 10132 KB Output is correct
9 Correct 10 ms 10132 KB Output is correct
10 Correct 14 ms 10264 KB Output is correct
11 Correct 11 ms 10300 KB Output is correct
12 Correct 10 ms 10452 KB Output is correct
13 Correct 832 ms 492028 KB Output is correct
14 Correct 830 ms 494124 KB Output is correct
15 Correct 1321 ms 494124 KB Output is correct
16 Correct 467 ms 494496 KB Output is correct
17 Correct 870 ms 496456 KB Output is correct
18 Correct 885 ms 498684 KB Output is correct
19 Correct 934 ms 500856 KB Output is correct
20 Correct 885 ms 502804 KB Output is correct
21 Correct 462 ms 504960 KB Output is correct
22 Correct 887 ms 507076 KB Output is correct
23 Correct 484 ms 509204 KB Output is correct
24 Correct 886 ms 511172 KB Output is correct
25 Correct 1322 ms 512416 KB Output is correct
26 Correct 857 ms 519008 KB Output is correct
27 Correct 839 ms 521092 KB Output is correct