oj.uz

Submission #972427

# Submission time Handle Problem Language Result Execution time Memory
972427 2024-04-30T12:01:42 Z Nika533 Dreaming (IOI13_dreaming) C++14
0 / 100
 39 ms 15832 KB 
#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

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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