제출 #625054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625054		Arnch	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	212 ms	50156 KiB

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<int, int> > 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 != 1) assert(0);

	preDFS(1);
	ans = sum;
//	DFS(1);

//	cout<<sum_t - ans <<endl;

	for(int i = 1; i <= n; i++) {
		ans = max(ans, sum + cnt[i][1] - cnt[i][0]);
	}

	cout<<sum_t - ans;

    return 0;
}

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