oj.uz

Submission #129182

# Submission time Handle Problem Language Result Execution time Memory
129182 2019-07-11T19:32:13 Z zeyad49 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 753 ms 62956 KB 
#include <bits/stdc++.h>
using namespace std;
#define v first
#define cost1 second.first
#define cost2 second.second
const int N=200001;
vector <pair<int,pair<int,int>>> adj[N];

vector<int> subTrees[N];
int timer,tin[N],tout[N];
long long totalUp,totalDown,down[N],up[N],maxNotInSub[N],maxDown[N],ans[N];
map<long long ,int> Map;

void dfs(int u, int p, int id) {
		tin[u] = timer++;
		long long max1=down[u];
		long long max2=0;
		maxDown[u] = down[u];
		subTrees[id].push_back(u);
		int newId = id;
		for (auto nxt : adj[u]) {
			int v = nxt.v;
			if (v == p)
				continue;
			up[v] = up[u] + nxt.cost2;
			totalUp += nxt.cost2;
			down[v] = down[u] + nxt.cost1;
			totalDown += nxt.cost1;
			dfs(v, u, p == -1 ? ++newId : newId);
			if(maxDown[v]>max2){
			    max2=maxDown[v];
			}
			if(max2>max1)
			    swap(max2,max1);
			maxDown[u] = max(maxDown[u], maxDown[v]);
		}
	
		tout[u] = timer - 1;
		Map[down[u]]++;
		ans[2]=max(ans[2],max1+max2-down[u]-up[u]);

	}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(NULL);
    int n;
    cin>>n;
	timer=0;

	for(int u=0;u<n;u++){
	    down[u]=0;
	    up[u]=0;
	    ans[u+1]=0;
	    maxNotInSub[u]=0;
	}
		for (int i = 1; i < n; i++) {
		    int u,v,c1,c2;
		    cin>>u>>v>>c1>>c2;
    u--;
    v--;
		    adj[u].push_back({v,{c1,c2}});
		  adj[v].push_back({u,{c2,c1}});
		
		}
		dfs(0, -1, 0);
		ans[2]+=totalUp;
		
		for (int col = 1; col < n; col++) {
			for (int u : subTrees[col]) {
			    Map[down[u]]--;
			    if(Map[down[u]]==0)
			        Map.erase(down[u]);
			}

			long long max=Map.rbegin()->first;
			for (int u : subTrees[col]) {
			    Map[down[u]]++;
				maxNotInSub[u] = max;
			}
		}
//		System.out.println(Arrays.toString(maxNotInSub));
		for (int u = 0; u < n; u++) {
			ans[1] = max(ans[1], totalUp - up[u] + down[u]);
// 			long long  curr = 0;
// 			// u and root
// 			curr = totalUp + down[u];
// 			ans[2] = max(ans[2], curr);
// 			// u and some child for u
// 			curr = totalUp - up[u] + maxDown[u];
// 			ans[2] = max(ans[2], curr);
// 			// u and some node v such that lca(v,u) = root
// 			curr = totalUp + down[u] + maxNotInSub[u];
// 			ans[2] = max(ans[2], curr);

		}
		int q;
		cin>>q;
		while (q-- > 0) {
		    int t;
		    cin>>t;
		    
			cout<<(totalUp + totalDown -ans[t])<<"\n";
		}
 }

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Incorrect 10 ms 9848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 537 ms 43260 KB Output is correct
3 Correct 498 ms 56004 KB Output is correct
4 Correct 416 ms 34792 KB Output is correct
5 Correct 682 ms 42580 KB Output is correct
6 Correct 424 ms 44740 KB Output is correct
7 Correct 749 ms 42408 KB Output is correct
8 Correct 501 ms 56620 KB Output is correct
9 Correct 695 ms 42972 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 545 ms 43376 KB Output is correct
3 Correct 554 ms 62956 KB Output is correct
4 Correct 409 ms 37736 KB Output is correct
5 Correct 753 ms 47052 KB Output is correct
6 Correct 425 ms 49516 KB Output is correct
7 Correct 650 ms 47252 KB Output is correct
8 Correct 513 ms 56428 KB Output is correct
9 Correct 644 ms 47412 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Incorrect 10 ms 9848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 537 ms 43260 KB Output is correct
3 Correct 498 ms 56004 KB Output is correct
4 Correct 416 ms 34792 KB Output is correct
5 Correct 682 ms 42580 KB Output is correct
6 Correct 424 ms 44740 KB Output is correct
7 Correct 749 ms 42408 KB Output is correct
8 Correct 501 ms 56620 KB Output is correct
9 Correct 695 ms 42972 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct
11 Correct 545 ms 43376 KB Output is correct
12 Correct 554 ms 62956 KB Output is correct
13 Correct 409 ms 37736 KB Output is correct
14 Correct 753 ms 47052 KB Output is correct
15 Correct 425 ms 49516 KB Output is correct
16 Correct 650 ms 47252 KB Output is correct
17 Correct 513 ms 56428 KB Output is correct
18 Correct 644 ms 47412 KB Output is correct
19 Correct 11 ms 9720 KB Output is correct
20 Incorrect 698 ms 47056 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Incorrect 10 ms 9848 KB Output isn't correct
3 Halted 0 ms 0 KB -