oj.uz

Submission #53577

# Submission time Handle Problem Language Result Execution time Memory
53577 2018-06-30T08:51:21 Z alenam0161 Dreaming (IOI13_dreaming) C++17
18 / 100
 85 ms 17784 KB 
# include "dreaming.h"
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include  <cmath>
#include <cstring>
using namespace std;
const int Mxn=1e5+7;
vector<int> g[Mxn],cost[Mxn];
bool used[Mxn];
int di[Mxn];
int cur=0;
void dfs(int v,int p){
    for(int i=0;i<g[v].size();++i){
        int to=g[v][i];
        int c=cost[v][i];
        if(to==p)continue;
        dfs(to,v);
        di[v]=max(di[v],di[to]+c);
    }
}
void go(int v,int p,int cp){
    int cs=-1;
    int e=0;
    int r=0;
    for(int i=0;i<g[v].size();++i){
        int to=g[v][i];
        int c=cost[v][i];
        if(to==p)continue;
        if(cs==-1||di[cs]+e<di[to]+c){
            if(cs!=-1){
                r=di[cs]+e;
            }
            cs=to;
            e=c;
        }
        else if(di[to]+c>r){
            r=di[to]+c;
        }
    }
    cur=min(cur,max(cp,di[v]));
   // cout<<v<<" "<<cp<<" "<<di[v]<<" "<<r<<endl;
     for(int i=0;i<g[v].size();++i){
        int to=g[v][i];
        int c=cost[v][i];
        if(to==p)continue;
        if(cs==to){
            go(to,v,max(cp,r)+c);
        }
        else{
            go(to,v,max(cp,cs==-1? 0:di[cs]+e));
        }
    }
}
void dfs_fill(int v,int p){
    used[v]=true;
    for(int i=0;i<g[v].size();++i){
        if(used[g[v][i]]==true)continue;
        dfs_fill(g[v][i],v);
    }
}
int travelTime (int N, int M, int L, int A[], int B[], int T[]) {
  memset(di,0,sizeof(di));
  memset(used,0,sizeof(used));
  for(int i=0;i<M;++i){
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
    cost[A[i]].push_back(T[i]);
    cost[B[i]].push_back(T[i]);
  }
  vector<int> z;
  for(int i=0;i<N;++i){
    if(used[i]==false){
        dfs(i,i);
        cur=1e9;
        go(i,i,0);
        z.push_back(cur);
        dfs_fill(i,i);
    }
  }
  sort(z.begin(),z.end());
  reverse(z.begin(),z.end());
  if(z.size()==1)return z[0];
  if(z.size()==2){
    return z[0]+L+z[1];
  }
  return max(z[0]+L+z[1],L+L+z[1]+z[2]);
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();++i){
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'void go(int, int, int)':
dreaming.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();++i){
                 ~^~~~~~~~~~~~
dreaming.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=0;i<g[v].size();++i){
                  ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs_fill(int, int)':
dreaming.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();++i){
                 ~^~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 10136 KB Output is correct
2 Correct 42 ms 10232 KB Output is correct
3 Correct 48 ms 10232 KB Output is correct
4 Correct 49 ms 10232 KB Output is correct
5 Correct 46 ms 10232 KB Output is correct
6 Correct 60 ms 10740 KB Output is correct
7 Correct 45 ms 10360 KB Output is correct
8 Correct 58 ms 10104 KB Output is correct
9 Correct 50 ms 10104 KB Output is correct
10 Correct 48 ms 10368 KB Output is correct
11 Correct 6 ms 5504 KB Output is correct
12 Correct 10 ms 6268 KB Output is correct
13 Correct 10 ms 6272 KB Output is correct
14 Correct 9 ms 6232 KB Output is correct
15 Correct 10 ms 6268 KB Output is correct
16 Correct 11 ms 6264 KB Output is correct
17 Correct 9 ms 6140 KB Output is correct
18 Correct 11 ms 6272 KB Output is correct
19 Correct 10 ms 6268 KB Output is correct
20 Correct 6 ms 5504 KB Output is correct
21 Correct 6 ms 5504 KB Output is correct
22 Correct 7 ms 5504 KB Output is correct
23 Correct 10 ms 6140 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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