Submission #105772

#	Time	Username	Problem	Language	Result	Execution time	Memory
105772		antimirage	Designated Cities (JOI19_designated_cities)	C++14	0 / 100	473 ms	40056 KiB

designated_cities

#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;

const int N = 2e5 + 5;

int n, x, y, c, d, q, u[N], tin[N], tout[N], timer, up[20][N];

vector < vector < pair < int, pair <int, int> > > > g;

long long ALL, ans[N], pref[2][N];

void dfs (int v, int p = 0)
{
	tin[v] = ++timer;
	up[0][v] = p;
	
	for (int i = 1; i < 20; i++)
		up[i][v] = up[i - 1][ up[i - 1][v] ];
	
	for (auto to : g[v]){
		if (to.fr == p) continue;
		
		pref[0][to.fr] = pref[0][v] + to.sc.fr;
		pref[1][to.fr] = pref[1][v] + to.sc.sc;
		
		ALL += to.sc.fr;
		
		dfs(to.fr, v);
	}
	tout[v] = ++timer;
}
bool upper (int a, int b)
{
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca (int a, int b)
{
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;
	
	for (int i = 19; i >= 0; i--){
		
		if (up[i][a] && !upper(up[i][a], b) )
			a = up[i][a];
	}
	return up[0][a];
}
inline long long calc (int cnt, int ind, int LCA)
{
	if (cnt == 1){
		return +pref[0][ind] - pref[1][ind];
	}
	else{
		return -1;
	}
}
main() {
	
	cin >> n;
	g.resize(n + 1);
	
	for (int i = 1; i < n; i++){
	
		scanf("%d%d%d%d", &x, &y, &c, &d);
		g[x].pb( mk(y, mk(c, d) ) );
		g[y].pb( mk(x, mk(d, c) ) );
	}
	dfs(1);
	
	int LCA = -1;
	
	for (int i = 1; i <= 1; i++){
		
		int mx = -1e9, ind = 0;
		
		for (int j = 1; j <= n; j++){
		
			if (u[j]) continue;
								
			/**if (i == 1){
				cout << calc(i, j, LCA) << " " << j << endl; 
			}**/
			if (calc(i, j, LCA) > mx){
				
				mx = calc(i, j, LCA);
				ind = j;
			}
		}
		u[ind] = 1;
		ans[i] = ans[i - 1] + mx;
		
		if (i == 1){
			LCA = ind;
		}
		else
			LCA = lca(LCA, ind);
	}	
	cin >> q;
	while (q--){
		scanf("%d", &x);
		cout << ALL - ans[x] << endl;
	}
}
/**
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2
**/

Compilation message (stderr)

designated_cities.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x, &y, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44