Submission #625064

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625064	2022-08-09T09:48:26 Z	Arnch	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	272 ms	68984 KB

designated_cities

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

ll sum_t, sum, ans;
ll cnt[N][2], dp[N];
vector<pair<ll, ll> > adj[N];

/*
   1 -> pain
   0 -> bala
*/

void preDFS(int x, int p = 0) {
	for(auto j : adj[x]) {
		if(j.first == p) {
			sum += j.second;
			cnt[x][0] = cnt[p][0] + j.second;
			break;
		}
	}
	for(auto j : adj[x]) {
		if(j.first == p) {
			continue;
		}
		cnt[j.first][1] = cnt[x][1] + j.second;
		preDFS(j.first, x);
	}
}
void DFS(int x, int p = 0) {
	vector<ll> vc;
	for(auto j : adj[x]) {
		if(j.first == p) {
			continue;
		}
		DFS(j.first, x);
		dp[x] = max(dp[x], j.second + dp[j.first]);
		vc.push_back(dp[j.first] + j.second);
	}
	sort(All(vc), greater<ll>());
	if(Sz(vc) >= 2) {
		ans = max(ans, sum + cnt[x][1] - cnt[x][0] + vc[0] + vc[1]);
	}
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n, q; cin >>n;
	for(int i = 0; i < n - 1; i++) {
		int u, v, c, d; cin >>u >>v >>c >>d;
		adj[u].push_back({v, c}), adj[v].push_back({u, d});
		sum_t += c, sum_t += d;
	}

	cin >>q;
	if(q != 1) assert(0);

	int e; cin >>e;
	if(e != 2) assert(0);

	if(n == 2) {
		return cout<<0, 0;
	}

	int ver = 1;
	for(int i = 1; i <= n; i++) if(Sz(adj[i]) > 1) {
		ver = i; break;
	}

	preDFS(ver);
	ans = sum;
	DFS(ver);

	cout<<sum_t - ans <<endl;


	return 0;
}

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	39 ms	48048 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	34 ms	48000 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23776 KB	Output is correct
2	Correct	252 ms	45052 KB	Output is correct
3	Correct	272 ms	68984 KB	Output is correct
4	Correct	266 ms	43828 KB	Output is correct
5	Correct	228 ms	45824 KB	Output is correct
6	Correct	264 ms	48608 KB	Output is correct
7	Correct	180 ms	47760 KB	Output is correct
8	Correct	261 ms	58408 KB	Output is correct
9	Correct	164 ms	46004 KB	Output is correct