oj.uz

답안 #424624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424624 2021-06-12T08:17:39 Z milleniumEeee Designated Cities (JOI19_designated_cities) C++14
0 / 100
 1733 ms 524292 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
//#define ll long long
#define int long long
 
template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}
 
using namespace std;
 

const int MAXN = (int)2e5 + 5;
const int L = 20;

vector <pii> g[MAXN];
vector <pii> G[MAXN];

int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int answer[MAXN];

int dist[MAXN];
int n;

void calc(int v, int par, int len = 0) {
	dist[v] = len;
	for (auto [to, cost] : G[v]) {
		if (to != par) {
			calc(to, v, len + cost);
		}
	}
}

int tin[MAXN], tout[MAXN];
int tiktak = 0;
int pr[MAXN][L + 1];

void precalc(int v, int par) {
	tin[v] = ++tiktak;
	pr[v][0] = par;
	for (int lv = 1; lv <= L; lv++) {
		pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
	}
	for (auto [to, cost] : g[v]) {
		if (to != v) {
			precalc(to, v);
		}
	}
	tout[v] = tiktak;
}

bool father(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int get_lca(int a, int b) {
	if (father(a, b)) {
		return a;
	}
	if (father(b, a)) {
		return b;
	}
	for (int lv = L; lv >= 0; lv--) {
		if (!father(pr[a][lv], b)) {
			a = pr[a][lv];
		}	
	}
	return pr[a][0];
}

void solve(int n, int a, int b) {
	
}

map <pii, int> edge;

int used[MAXN][2], used_id = 0;
 
void add(int x, int color) {
	for (int i = 1; i < n; i++) {
		int a = A[i];
		int b = B[i];
		if (father(a, b)) {
			if (father(b, x)) {
				used[i][0] = color;
			} else {
				used[i][1] = color;
			}
		}
		else {
			if (father(a, x)) {
				used[i][1] = color;
			}
			else {
				used[i][0] = color;
			}
		}
	}
}

int center[MAXN];

void calc_center(int v, int par, int cur_sum) {
	center[v] = cur_sum;
	for (auto [to, cost] : g[v]) {
		if (to != par) {
			multiset <int> st;
			int ed = edge[{v, to}];
			st.insert(C[ed]);
			st.insert(D[ed]);
			int cur_cost;
			auto it = st.begin();
			if (*it == cost) {
				it++;
			}
			cur_cost = *it;
			calc_center(to, v, cur_sum - cur_cost + cost);
		}
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		edge[{b, a}] = edge[{a, b}] = i;
		g[a].pb({b, c});
		g[b].pb({a, d});
		G[a].pb({a + b, c});
		G[b].pb({a + b, d});
	}
	
	// calc tin tout
	precalc(1, 1);
	
	// case e[i] = 1
	{
		used_id = 1;
		add(1, used_id);
		int sum_root = 0;
		int edge_sum = 0;
		for (int i = 1; i < n; i++) {
			if (used[i][0] == used_id) {
				sum_root += C[i];
			}
			if (used[i][1] == used_id) {
				sum_root += D[i];
			}
			edge_sum += C[i] + D[i];
		}
		calc_center(1, -1, sum_root);
		int big = 1;
		for (int i = 1; i <= n; i++) {
			if (center[i] > center[big]) {
				i = big;
			}
		}
		answer[1] = edge_sum - center[big]; 
		cout << answer[1] << endl;
		exit(0);
	}
	
	calc(1, -1);
	int a = 1;
	for (int i = 1; i <= n; i++) {
		if (dist[i] > dist[a]) {
			a = i;
		}
	}
	calc(a, -1);
	int b = 1;
	for (int i = 1; i <= n; i++) {
		if (dist[i] > dist[b]) {
			b = i;
		}
	}
	// a и b наш диаметр
	solve(n, a, b);
	
}

Compilation message

designated_cities.cpp: In function 'void calc(long long int, long long int, long long int)':
designated_cities.cpp:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |  for (auto [to, cost] : G[v]) {
      |            ^
designated_cities.cpp: In function 'void precalc(long long int, long long int)':
designated_cities.cpp:49:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |  for (auto [to, cost] : g[v]) {
      |            ^
designated_cities.cpp: In function 'void calc_center(long long int, long long int, long long int)':
designated_cities.cpp:110:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |  for (auto [to, cost] : g[v]) {
      |            ^

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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