oj.uz

답안 #20404

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20404 2017-02-11T04:55:23 Z Namnamseo 구슬과 끈 (APIO14_beads) C++14
0 / 100
 26 ms 19200 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pp;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define pb push_back
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args> void read(T& a,Args&... b){ read(a); read(b...); }

const int max_n = 200010;
const ll inf = 1LL<<60;

vector<pp> edge[max_n];
map<pp, int> ed;
int par[max_n];

ll   dp [max_n][3][2];
bool chk[max_n][3][2];

int n;

void in(){
	read(n);
	for(int i=1; i<n; ++i){
		int x, y, d; read(x, y, d);
		edge[x].pb({y, d});
		edge[y].pb({x, d});
		ed[{x, y}] = d;
		ed[{y, x}] = d;
	}
}

vector<int> nin[max_n];
ll osum[max_n];
multiset<ll> mev[max_n];

void dfs(int x){
	for(pp tmp:edge[x]){
		int y=tmp.first;
		if(par[x]!=y) par[y]=x, nin[x].pb(y), dfs(y);
	}
	if(par[x]) nin[x].pb(par[x]);
}

ll f(int, int, int);

int vc[max_n];
int lf[max_n];
int ld[max_n];

void fill_val(int p, int from){
	if(lf[p] == from) return;
	if(vc[p] == 0){
		for(pp tmp:edge[p]){
			int x, dst;
			tie(x, dst)=tmp;
			if(x == from){
				ld[p]=dst;
				continue;
			}
			ll ov = max(f(x, p, 0), dst + f(x, p, 1));
			osum[p] += ov;
			mev[p].insert(dst + f(x, p, 0) - ov);
		}
	} else {
		if(lf[p] != -1){
			int x=lf[p], dst=ld[p];
			ll ov = max(f(x, p, 0), dst + f(x, p, 1));
			osum[p] += ov;
			mev[p].insert(dst + f(x, p, 0) - ov);
		}
		if(from != -1){
			int x=from, dst=ed[pp{from, p}];
			ll ov = max(f(x, p, 0), dst + f(x, p, 1));
			osum[p] -= ov;
			mev[p].erase(mev[p].find(dst + f(x, p, 0) - ov));
			ld[p]=dst;
		}
	}
	++vc[p];
	lf[p]=from;
}

ll f(int p, int from, int parity){
	int child=(from == -1) ? p : (par[from]==p ? from:p);
	int sec = (from == -1) ? 2 : (p==child);
	ll& mydp = dp[child][sec][parity];
	if(chk[child][sec][parity]) return mydp;
	chk[child][sec][parity]=1;
	mydp = -inf;
    
	fill_val(p, from);
	if(parity == 0){
		mydp = osum[p];
	} else {
		if(mev[p].size())
			mydp = osum[p] + *--mev[p].end();
	}
	
	return mydp;
}

int main()
{
	freopen("in", "r", stdin);
	in(); dfs(1);
	ll ans = 0;
	for(int i=1; i<=n; ++i){
		multiset<ll> diff;
		for(auto tmp:edge[i]){
			int y, d; tie(y, d) = tmp;
			ll v = d+f(y, i, 0);
			v -= max(f(y, i, 0), d+f(y, i, 1));
			diff.insert(v);
			if(diff.size() == 3u) diff.erase(diff.begin());
		}
		ll mv = f(i, -1, 0);
		ans = max(ans, mv);
		if(diff.size() >= 2u){
			auto it=diff.rbegin();
			auto i2=it; ++i2;
			ans = max(ans, mv + *it + *i2);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

beads.cpp: In function 'void read(int&)':
beads.cpp:7:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:105:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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