oj.uz

Submission #163516

# Submission time Handle Problem Language Result Execution time Memory
163516 2019-11-13T17:07:45 Z kostia244 Dreaming (IOI13_dreaming) C++17
0 / 100
 74 ms 21500 KB 
#define _GLIBCXX_DEBUG
#include "dreaming.h"
#include<bits/stdc++.h>
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;
int n;
vvpi g;
vi diams, comp;
bitset<5000> vis;
void dc(int v) {
	comp.pb(v);
	vis.set(v);
	for(auto i : g[v])
		if(!vis.test(i.first)) dc(i.first);
}
ll dfs(int v, int p) {
	ll x=0;
	for(auto i : g[v])
		if(i.first!=p) x = max(x, i.second+dfs(i.first, v));
	return x;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	if(n==1)
		return 0;
	n = N;
	g.resize(n);
	ll ans = 0;
	for(int f, t, c, i = 0; i < M; i++) {
		f = A[i], t = B[i], c = T[i];
		g[f].pb({t, c});
		g[t].pb({f, c});
//		cout <<f << " " <<t << "\n";
	}
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			comp.clear();
			dc(i);
			ll d = LLONG_MAX;
			for(auto j : comp)
				d = min(d, dfs(j, j));
			diams.pb(d);
		}
	}
	sort(rall(diams));
	if(diams.size()==1)ans=diams[0];
	else ans = diams[0]+L+diams[1];
	if(diams.size()>2) ans = max(ans, diams[2]+L+L+diams[1]);
	return ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 21500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 21500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 21500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 15708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 21500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 21500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -