Submission #895904

#	Time	Username	Problem	Language	Result	Execution time	Memory
895904		ByeWorld	Dreaming (IOI13_dreaming)	C++14	0 / 100	39 ms	19764 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 2e5+10;
const int INF = 2e9;

int n, m, l, ans;
vector <pii> adj[MAXN];
int cc[MAXN], mx[MAXN];

int dw[MAXN], up[MAXN]; // max ke bawah, ke par (atas)
void dfs(int nw, int par){
	for(auto ed : adj[nw]){
		int nx = ed.fi; int wei = ed.se;
		dw[nw] = max(dw[nw], 0);
		if(nx==par) continue;
		dfs(nx, nw);
		dw[nw] = max(dw[nw], dw[nx]+wei);
	}
}

multiset <int> mul;
void bui(int nw, int par){
	for(auto ed : adj[nw]){ // build child nya aj
		int nx = ed.fi; int wei = ed.se;
		if(nx==par) continue; 
		//build
		mul.insert(dw[nx]+wei);
	}
	for(auto ed : adj[nw]){ 
		int nx = ed.fi; int wei = ed.se;
		if(nx==par) continue; 
		//build
		auto it = mul.find(dw[nx]+wei);
		mul.erase(it);

		int mx = up[nw]; // up skrg
		if(!mul.empty()){
			it = mul.end(); it--;
			mx = max(mx, (*it));
		}
		up[nx] = mx+wei; // maxnya + wei buat ke child
		//cout << nx << ' '<< up[nx] << " p\n";

		mul.insert(dw[nx]+wei);
	}

	mul.clear();
	for(auto ed : adj[nw]){ // build child nya aj
		int nx = ed.fi; int wei = ed.se;
		if(nx==par) continue; 
		bui(nx, nw);
	}
	ans = max(ans, up[nw]);
}

int root;
void rep(int nw, int par){
	cc[root] = min(cc[root], mx[nw]);
	for(auto ed : adj[nw]){ // build child nya aj
		int nx = ed.fi; int wei = ed.se;
		if(nx==par) continue; 
		rep(nx, nw);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N; m = M; l = L;
	for(int i=0; i<m; i++){
		adj[A[i]+1].pb({B[i]+1, T[i]});
		adj[B[i]+1].pb({A[i]+1, T[i]});
	}
	for(int i=1; i<=n; i++){
		up[i] = -1; dw[i] = -1; mx[i] = INF; cc[i] = INF;
	}
	for(int i=1; i<=n; i++){
		if(up[i]!=-1) continue;
		dfs(i, 0);
		bui(i, 0);
	}
	for(int i=1; i<=n; i++){
		mx[i] = max(up[i], dw[i]);
	}

	vector <int> vec;
	for(int i=1; i<=n; i++){
		if(up[i]==-1){
			root = i;
			rep(i, 0);
			vec.pb(cc[i]);
		}
	}
	ans = max(ans, vec[0]+vec[1]+l);
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void bui(int, int)':
dreaming.cpp:55:23: warning: unused variable 'wei' [-Wunused-variable]
   55 |   int nx = ed.fi; int wei = ed.se;
      |                       ^~~
dreaming.cpp: In function 'void rep(int, int)':
dreaming.cpp:66:23: warning: unused variable 'wei' [-Wunused-variable]
   66 |   int nx = ed.fi; int wei = ed.se;
      |                       ^~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23