oj.uz

답안 #173357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173357 2020-01-03T19:13:26 Z ZwariowanyMarcin Designated Cities (JOI19_designated_cities) C++14
0 / 100
 857 ms 26472 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 2e5 + 111;

int n, nn;
int a, b, c, d;
vector <pair<int,int>> v[nax];
ll all;
ll ans[nax];

int died[nax];
int siz[nax];

void dfs(int u, int p) {
	siz[u] = 1;
	nn++;
	for(auto it : v[u]) 
		if(it.fi != p && !died[it.fi]) {
			dfs(it.fi, u);
			siz[u] += siz[it.fi];
		}
}

int daj(int u, int p) {
	for(auto it : v[u]) 
		if(it.fi != p && !died[it.fi] && nn <= 2 * siz[it.fi])
			return daj(it.fi, u);
	return u;
}

ll oblicz(int u, int p) {
	ll sum = 0;
	for(auto it : v[u]) {
		if(it.fi == p) sum += it.se;
		else if(!died[it.fi])
			sum += oblicz(it.fi, u);
	}
	return sum;
}

ll dp[nax];
	
void makedp(int u, int p) {
	dp[u] = 0;
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi]) {
			makedp(it.fi, u);
			dp[u] = max(dp[u], dp[it.fi] + it.se);
		}
}

vector <pair<ll, int>> vec;

void go(int u, int p, ll cost = 0, int anc = -1) {
	tuple <ll, int, int> best = make_tuple(-1, 0, 0);
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi])
			best = max(best, make_tuple(dp[it.fi] + it.se, it.fi, it.se));
	if(get<0> (best) != -1)
		go(get<1> (best), u, cost + get<2> (best), (anc == -1 ? get<1> (best) : anc));
	else
		vec.pb(mp(cost, anc));
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi] && it.fi != get<1> (best))
			go(it.fi, u, it.se, (anc == -1 ? it.fi : anc));
}

ll o[nax];
	
void solve(int u) {
	ll cnt = o[u];
	makedp(u, 0);
	go(u, 0);
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	int h = 0;
	for(int i = 0; i < ss(vec); ++i) {
		if(vec[i].se != vec[0].se) h = 1;
		if(!h) ans[i + 2] = max(ans[i + 2], (cnt += vec[i].fi));
		else ans[i + 1] = max(ans[i + 1], (cnt += vec[i].fi));
	}
	vec.clear();
}
	
void pro(int u, int p, ll cost) {
	ll k = 0;
	for(auto it : v[u]) {
		if(it.fi != p)
			pro(it.fi, u, cost + it.se);
		else
			k = it.se;
	}
	cost -= k;
	o[u] = cost;
	ans[1] = max(ans[1], o[u]);
}
			

void decomp(int u) {
	nn = 0;
	dfs(u, 0);
	int c = daj(u, 0);
	solve(c);
	died[c] = 1;
	for(auto it : v[c])
		if(!died[it.fi])
			decomp(it.fi);
}
	
			
int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		v[a].pb(mp(b, c));
		v[b].pb(mp(a, d));
		all += c + d;
	}
	
	o[1] = oblicz(1, 0);
	pro(1, 0, o[1]);
	
	decomp(1);
	
	for(int i = 1; i <= n; ++i)
		ans[i] = max(ans[i], ans[i - 1]);
	
	int q;
	scanf("%d", &q);
	while(q--) {
		scanf("%d", &a);
		printf("%lld\n", all - ans[a]);
	}
	

	return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 799 ms 26468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Incorrect 857 ms 26472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 799 ms 26468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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