Submission #102516

#	Time	Username	Problem	Language	Result	Execution time	Memory
102516		Bruteforceman	Designated Cities (JOI19_designated_cities)	C++11	100 / 100	819 ms	54380 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
int n;
int l[500010], r[500010], a[500010], b[500010];
vector <int> g[500010];
long long sum;

typedef pair <long long, int> pii;
long long ans[500010];
pii opt[500010];
long long cost[500010];
vector <int> ls;
int root;
int Px, Py;

const long long inf = 1e17;

void leaves(int x, int par) {
	bool leaf = true;
	for(auto i : g[x]) {
		int y = l[i] ^ r[i] ^ x;
		if(y - par) {
			leaves(y, x);
			leaf = true;
		}
	}
	if(leaf) {
		ls.push_back(x);
	}
}

bool cmp(int x, int y) {
	return cost[x] > cost[y];
}

void dfs(int x, int par, long long add) {
	ans[1] = max(ans[1], add);

	opt[x] = pii(0, x);
	vector <pii> can;
	for(auto i : g[x]) {
		int y = l[i] ^ r[i] ^ x;
		int val = (y == r[i]) ? a[i] : b[i];
		if(y == par) continue;
		sum += val;
		dfs(y, x, add + val - (a[i] ^ b[i] ^ val));
		pii nw = pii(opt[y].first + val, opt[y].second);
		opt[x] = max(opt[x], nw);
		can.push_back(nw);
	}
	sort(can.begin(), can.end(), greater <pii> ());
	if(can.size() < 2) return ;
	if(ans[2] <= can[0].first + can[1].first + add) {
		ans[2] = can[0].first + can[1].first + add;
		root = x;
		Px = can[0].second;
		Py = can[1].second;
	}
}

void solve(int x, int par, long long add) {
	opt[x] = pii(0, x);
	for(auto i : g[x]) {
		int y = l[i] ^ r[i] ^ x;
		int val = (y == r[i]) ? a[i] : b[i];
		if(y == par) continue;
		sum += val;
		solve(y, x, add + val - (a[i] ^ b[i] ^ val));
		pii nw = pii(opt[y].first + val, opt[y].second);
		opt[x] = max(opt[x], nw);
		cost[opt[y].second] += val;
	}
}



int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        scanf("%d %d %d %d", &l[i], &r[i], &a[i], &b[i]);
        g[l[i]].emplace_back(i);
        g[r[i]].emplace_back(i);
    }
    root = 1;
    while(root < n && g[root].size() == 1) {
    	++root;
    }
    dfs(root, 0, 0);
    if(n == 2) {
    	ans[2] = sum;
    } 
    ans[1] = sum - ans[1];
    ans[2] = sum - ans[2];

    sum = 0;
    solve(root, 0, 0);
    leaves(root, 0);
    
    long long Pcx = cost[Px];
    long long Pcy = cost[Py];
    cost[Px] = inf;
    cost[Py] = inf;
    sort(ls.begin(), ls.end(), cmp);
    cost[Px] = Pcx;
    cost[Py] = Pcy;

    long long tot = 0;
    for(int i = 1; i <= ls.size(); i++) {
    	tot += cost[ls[i - 1]];
    	if(i > 2) {
    		ans[i] = max(ans[i], tot);
    	}
    } 
    for(int i = 3; i <= ls.size(); i++) {
    	ans[i] = sum - ans[i];
    }

    int q;
    scanf("%d", &q);

    while(q--) {
    	int x;
    	scanf("%d", &x);
    	printf("%lld\n", ans[x]);
    }
    return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i <= ls.size(); i++) {
                    ~~^~~~~~~~~~~~
designated_cities.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 3; i <= ls.size(); i++) {
                    ~~^~~~~~~~~~~~
designated_cities.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
designated_cities.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &l[i], &r[i], &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
designated_cities.cpp:123:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &x);
      ~~~~~^~~~~~~~~~

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