oj.uz

Submission #625062

# Submission time Handle Problem Language Result Execution time Memory
625062 2022-08-09T09:47:17 Z Arnch Designated Cities (JOI19_designated_cities) C++17
0 / 100
 33 ms 48100 KB 
// 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) assert(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 33 ms 48004 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 33 ms 48060 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

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