oj.uz

Submission #492230

# Submission time Handle Problem Language Result Execution time Memory
492230 2021-12-06T02:48:21 Z PoPularPlusPlus Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 65540 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

const int N = 100003;

int sum[N];
vector<pair<int,int>> adj[N];
bool vis[N];
int ans;

void dfs1(int node , int par){
	vis[node] = 1;
	sum[node] = 0;
	for(auto i : adj[node]){
		if(i.vf != par){
			dfs1(i.vf , node);
			sum[node] += sum[i.vf];
		}
	}
}

int dfs(int node , int up , int par){
	vector<int> v;
	for(auto i : adj[node]){
		if(i.vf != par){
			v.pb(i.vs + sum[i.vf]);
		}
	}
	sv(v);
	if(v.size() == 0)return up;
	int res = max(up , v.back());
	if(v.size() == 1)ans = max(ans , v.back() + up);
	else ans = max(ans , v.back() + max(up , v[v.size()-2]));
	for(auto i : adj[node]){
		if(i.vf!=par){
			if(i.vs + sum[i.vf] == v.back()){
				int x = up;
				if(v.size() > 1)x = max(x , v[v.size()-2]);
				res = min(res , dfs(i.vf , x + i.vs , node));
			}
			else res = min(res , dfs(i.vf , max(up , v.back()) + i.vs , i.vf));
		}
	}
	return res;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
   memset(sum,0,sizeof sum);
   memset(vis,0,sizeof vis);
   ans = 0;
   cout << n << '\n';
   for(int i = 0; i < m; i++){
	   adj[a[i]].pb(mp(b[i] , t[i]));
	   adj[b[i]].pb(mp(a[i] , t[i]));
   }
   vector<int> v;
   for(int i = 0; i < n; i++){
	   if(!vis[i]){
		   dfs1(i,-1);
		   //cout << "came" << endl;
		   v.pb(dfs(i,0,-1));
		   //cout << "came1" << endl;
	   }
   }
   sv(v);
   if(v.size() > 1)
   ans = max(ans , v[0] + v.back());
   return ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 16312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 16312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 16312 KB Time limit exceeded
2 Halted 0 ms 0 KB -