Submission #895911

#	Time	Username	Problem	Language	Result	Execution time	Memory
895911		ByeWorld	Dreaming (IOI13_dreaming)	C++14	100 / 100	72 ms	27324 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 arr[MAXN];
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++){
		mx[i] = INF; cc[i] = INF;
	}
	for(int i=1; i<=n; i++){
		if(up[i]!=0) continue;
		dfs(i, 0);
		bui(i, 0);
	}
	for(int i=1; i<=n; i++){
		mx[i] = max(up[i], dw[i]);
	}

	vector <int> vec; // isinya worst case ambil path
	for(int i=1; i<=n; i++){
		if(up[i]==0){
			root = i;
			rep(i, 0);
			vec.pb(cc[i]);
		}
	}
	sort(vec.begin(), vec.end()); int siz = vec.size();
	vector <int> build;
	for(int i=0; i<siz; i++){
		if(i==vec.size()-1){
			build.pb(vec[i]);
		} else {
			build.pb(vec[i]+l);
		}
	}
	sort(build.begin(), build.end());
	//cout << vec[0] << ' ' << vec[1] << " p\n";
	if(siz>=2) ans = max(ans, build[siz-1]+build[siz-2]);
	else ans = max(ans, build[0]);
    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;
      |                       ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:102:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   if(i==vec.size()-1){
      |      ~^~~~~~~~~~~~~~

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