oj.uz

Submission #895904

# Submission time Handle Problem Language Result Execution time Memory
895904 2023-12-31T04:17:40 Z ByeWorld Dreaming (IOI13_dreaming) C++14
0 / 100
 39 ms 19764 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 19764 KB Output is correct
2 Correct 39 ms 19288 KB Output is correct
3 Correct 29 ms 18512 KB Output is correct
4 Correct 7 ms 10584 KB Output is correct
5 Correct 6 ms 10076 KB Output is correct
6 Correct 11 ms 11652 KB Output is correct
7 Incorrect 2 ms 9048 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9196 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Incorrect 2 ms 9052 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 19764 KB Output is correct
2 Correct 39 ms 19288 KB Output is correct
3 Correct 29 ms 18512 KB Output is correct
4 Correct 7 ms 10584 KB Output is correct
5 Correct 6 ms 10076 KB Output is correct
6 Correct 11 ms 11652 KB Output is correct
7 Incorrect 2 ms 9048 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9196 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9048 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Incorrect 2 ms 9052 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 19764 KB Output is correct
2 Correct 39 ms 19288 KB Output is correct
3 Correct 29 ms 18512 KB Output is correct
4 Correct 7 ms 10584 KB Output is correct
5 Correct 6 ms 10076 KB Output is correct
6 Correct 11 ms 11652 KB Output is correct
7 Incorrect 2 ms 9048 KB Output isn't correct
8 Halted 0 ms 0 KB -