oj.uz

답안 #625054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625054 2022-08-09T09:37:58 Z Arnch Designated Cities (JOI19_designated_cities) C++17
7 / 100
 212 ms 50156 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<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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 47988 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 172 ms 40604 KB Output is correct
3 Correct 195 ms 49728 KB Output is correct
4 Correct 154 ms 39244 KB Output is correct
5 Correct 212 ms 40588 KB Output is correct
6 Correct 171 ms 41980 KB Output is correct
7 Correct 161 ms 40668 KB Output is correct
8 Correct 208 ms 50156 KB Output is correct
9 Correct 120 ms 41160 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 48012 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 47988 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 172 ms 40604 KB Output is correct
3 Correct 195 ms 49728 KB Output is correct
4 Correct 154 ms 39244 KB Output is correct
5 Correct 212 ms 40588 KB Output is correct
6 Correct 171 ms 41980 KB Output is correct
7 Correct 161 ms 40668 KB Output is correct
8 Correct 208 ms 50156 KB Output is correct
9 Correct 120 ms 41160 KB Output is correct
10 Runtime error 32 ms 48012 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 47988 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -