Submission #492230

#	Time	Username	Problem	Language	Result	Execution time	Memory
492230		PoPularPlusPlus	꿈 (IOI13_dreaming)	C++17	0 / 100	1089 ms	65540 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] += 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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23