oj.uz

Submission #384998

# Submission time Handle Problem Language Result Execution time Memory
384998 2021-04-02T21:28:24 Z ritul_kr_singh Traffic (IOI10_traffic) C++17
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;

const int MAXN = 1e6;
vector<vector<int>> g;
int sub[MAXN], sum = 0, curr = 0, ans = 1e18;

int dfs0(int u, int par){
	for(int v : g[u]) if(v != par){
			sub[u] += dfs0(v, u);
			curr = max(curr, sub[v]);
	}
	return sub[u];
}

void dfs1(int u, int par){
	ans = min(ans, curr);
	for(int v : g[u]){
		if(v==par) continue;
		int prev = curr;
		curr = max(curr, sum - sub[v]);
		dfs1(v, u);
		curr = prev;
	}
}

int LocateCentre(int n, int pop[], int S[], int D[]){
	for(int i=0; i<n; ++i) sum += (sub[i] = pop[i]);
	g.resize(n);
	for(int i=0; i<n-1; ++i){
		g[S[i]].push_back(D[i]);
		g[D[i]].push_back(S[i]);
	}
	dfs0(0, 0);
	dfs1(0, 0);
	return ans;
}

Compilation message

traffic.cpp:7:41: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | int sub[MAXN], sum = 0, curr = 0, ans = 1e18;
      |                                         ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -