Submission #492233

#	Time	Username	Problem	Language	Result	Execution time	Memory
492233		PoPularPlusPlus	Dreaming (IOI13_dreaming)	C++17	100 / 100	83 ms	24408 KiB

dreaming

#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] = max(sum[node] , sum[i.vf] + i.vs);
		}
	}
}

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 , node));
		}
	}
	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;
   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() == 2)
   ans = max(ans ,v[v.size()-2] + v.back() + l);
   else if(v.size() >= 3)ans = max(ans , max(v[v.size()-2] + v[v.size()-3] + l + l , v[v.size()-2] + v.back() + l));
   return ans;
}
/*
int main(){
	int n , m , l;
	cin >> n >> m >> l;
	int a[m],b[m],c[m];
	for(int i = 0; i < m; i++)cin >> a[i] >> b[i] >> c[i];
	cout << travelTime(n , m , l , a , b , c) << '\n';
}
*/

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