oj.uz

Submission #157541

# Submission time Handle Problem Language Result Execution time Memory
157541 2019-10-12T10:04:27 Z GioChkhaidze Dreaming (IOI13_dreaming) C++14
0 / 100
 75 ms 19180 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define Pb push_back
using namespace std;
const int N=2e5+5;
long long res,X,n,m,l,ko,Y,Res,f[N];
vector < pair < long long  , long long > > v[N];
vector < long long > V,G;

void Dfs(long long x,long long p,long long val,long long j) {
    if (res<=val) { X=x; res=val; }
    f[x]=j;
    for (int i=0; i<v[x].size(); i++)
        if (f[v[x][i].F]!=j && v[x][i].F!=p) Dfs(v[x][i].F,x,val+v[x][i].S,j);
}

void Df(long long x,long long p,long long val,long long j) {
    if (ko) { V.push_back(val); return ; }
    if (x==Y) { ko=1; return ; }
    f[x]=j;
    for (int i=0; i<v[x].size(); i++)
        if (f[v[x][i].F]!=j && v[x][i].F!=p) {
            Df(v[x][i].F,x,val+v[x][i].S,j);
            if (ko) { V.push_back(val); return ; }
        }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	int n=N,m=M,l=L;
	 for (int i=0; i<m; i++) {
        v[A[i]].Pb({B[i],T[i]});
        v[B[i]].Pb({A[i],T[i]});
    }
    
    for (int i=0; i<n; i++)
        if (!f[i]) {
            V.clear();
            res=0,X=0,Y=0,ko=0;

            Dfs(i,i,0,1);
            res=0,Y=X;
            Dfs(X,X,0,2);
            Res=max(Res,res);
            Df(X,X,0,3);

            long long Nq=1e13;
            for (int j=0; j<V.size(); j++)
                Nq=min(Nq,max(res-V[j],V[j]));

            if (Nq==1e13) Nq=0;

            G.push_back(Nq);
        }
        
    sort(G.begin(),G.end());

    if (G.size()==1) { cout<<Res<<endl; return 0; }
    if (G.size()==2) { cout<<max(Res,G[0]+G[1]+l)<<endl; return 0; }

    return max(Res,max(G[G.size()-1]+G[G.size()-2]+l,G[G.size()-3]+G[G.size()-2]+2*l));
}

Compilation message

dreaming.cpp: In function 'void Dfs(long long int, long long int, long long int, long long int)':
dreaming.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v[x].size(); i++)
                   ~^~~~~~~~~~~~
dreaming.cpp: In function 'void Df(long long int, long long int, long long int, long long int)':
dreaming.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v[x].size(); i++)
                   ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:49:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=0; j<V.size(); j++)
                           ~^~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9328 KB Output is correct
2 Correct 34 ms 9204 KB Output is correct
3 Correct 35 ms 9080 KB Output is correct
4 Correct 33 ms 9172 KB Output is correct
5 Correct 31 ms 9084 KB Output is correct
6 Correct 46 ms 9844 KB Output is correct
7 Correct 37 ms 9336 KB Output is correct
8 Correct 32 ms 9080 KB Output is correct
9 Correct 34 ms 9076 KB Output is correct
10 Correct 37 ms 9332 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 12 ms 7028 KB Output is correct
13 Correct 13 ms 7040 KB Output is correct
14 Correct 12 ms 7028 KB Output is correct
15 Correct 13 ms 7024 KB Output is correct
16 Correct 12 ms 7024 KB Output is correct
17 Correct 12 ms 6768 KB Output is correct
18 Correct 13 ms 6996 KB Output is correct
19 Correct 12 ms 6900 KB Output is correct
20 Incorrect 6 ms 4984 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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