Submission #972427

#	Time	Username	Problem	Language	Result	Execution time	Memory
972427		Nika533	Dreaming (IOI13_dreaming)	C++14	0 / 100	39 ms	15832 KiB

dreaming

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#include "dreaming.h"
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>

using namespace std;

const int NMAX=1e5+5;
int n,m,fix[NMAX],mx[NMAX],NEXT[NMAX];
vector<pii> g[NMAX];

void dfs(int x, int p) {
	mx[x]=0; NEXT[x]=-1; fix[x]=1;
	if (x!=p && g[x].size()==1) return;
	for (auto A:g[x]) {
		int y=A.f,w=A.s;
		if (y==p) continue;
		dfs(y,x);
		if (mx[x]<w+mx[y]) {
			mx[x]=w+mx[y];
			NEXT[x]=y;
		}
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n=N; m=M;
	for (int i=0; i<m; i++) {
		int a=A[i],b=B[i],c=T[i];
		g[a].pb({b,c}); g[b].pb({a,c});
	}
	
	//subtask 1 & 2 & 3
	
	int ans=L;
	
	for (int i=0; i<n; i++) {
		if (fix[i]==0) {
			
			vector<int> v;
			
			dfs(i,i);
			int j=i;
			while (j>=0) {
				v.pb(j); j=NEXT[j]; 
			}
			
			int st=v.back(); v.clear();
			
			dfs(st,st);
			j=st;
			while (j>=0) {
				v.pb(j); j=NEXT[j];
			}
			
			int d=mx[st],mn=1e9;
			for (auto x:v) {
				mn=min(mn,max(mx[x],d-mx[x]));
			}
			ans+=mn;
		}
	}
	return ans;
}

Compilation message (stderr)

dreaming.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~

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