Submission #235196

#	Time	Username	Problem	Language	Result	Execution time	Memory
235196		crossing0ver	Dreaming (IOI13_dreaming)	C++17	100 / 100	123 ms	35960 KiB

dreaming

#include<bits/stdc++.h>
#define fi first
#define se second
#include "dreaming.h"
using namespace std;

vector<pair<int,int> > adj[1000000];
pair <int,int> par[100000];
int n,m,component, dis[100000],mx,start,end1,timer,tin[100000],tout[100000],ans ,comp[100000] , day;

int vis[100000];
void dfs (int v,int p,int val) {
	if (dis[v] > mx) {
		mx = dis[v];
		start = v;
	}
	par[v] = {p,val};
	for (auto i : adj[v]) {
		if (i.fi != p) {
			dis[i.fi] = dis[v] + i.se;
			vis[i.fi] = vis[v];
			dfs (i.fi, v, i.se);
		}
	}
}
void get_mid (int a,int b) {
 // b is root
 int distance = dis[a],down = 0;
 ans = max (ans, distance);
 comp[component]  = distance;
 int mn = INT_MAX;
 while (a != b) {
	 down += par[a].se;
	 distance -= par[a].se;
	 mn = min (mn , max (down,distance));
	 a = par[a].fi;
	}
	if (mn == INT_MAX)
	comp[component] = 0;
	else comp[component] = mn;
}		
int make_components() {
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			mx = INT_MIN;
			component++;
			vis[i] = (i ? vis[i-1] + 1 : 1);
			dfs(i,-1,0);
			end1 = start;
			dis[start] = 0;
			mx = INT_MIN; 
			dfs (end1,-1,0);
			get_mid(start,end1);
		}
	}
	int mn = comp[1],in = 1;
	sort (comp + 1, comp + component + 1);
	if (component == 1) return ans;
	if (component == 2) {
		return max (ans, comp[1] + comp[2] + day);
	}
	return max (ans, max (day*2 +  comp[component - 1] + comp [component - 2], day + comp[component - 1] + comp [component]));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N; m = M;  day = L;
	for (int i = 0; i < m; i++) {
		adj[A[i]].push_back( { B[i], T[i] });
		adj[B[i]].push_back( { A[i], T[i] });
	}       
	return make_components();
}     /*
main () {
	int N,M,L;
	cin >> N >> M >> L;
	int A[M],B[M],T[M];
	for (int i = 0; i < M; i++)
		cin >> A[i] >> B[i] >> T[i] ;
	cout << travelTime(N, M, L, A, B, T);
}            */

Compilation message (stderr)

dreaming.cpp: In function 'int make_components()':
dreaming.cpp:56:6: warning: unused variable 'mn' [-Wunused-variable]
  int mn = comp[1],in = 1;
      ^~
dreaming.cpp:56:19: warning: unused variable 'in' [-Wunused-variable]
  int mn = comp[1],in = 1;
                   ^~

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