oj.uz

답안 #53570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53570 2018-06-30T08:27:05 Z alenam0161 꿈 (IOI13_dreaming) C++17
0 / 100
 83 ms 16248 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];
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);
    }
}
int go(int v,int p,int cp){
    int cs=-1;
    int e=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){
            cs=to;
            e=c;
        }
    }
 //   cout<<v<<" "<<cp<<" "<<cs<<endl;
    if(cs!=-1){
        int q=0;
        for(int i=0;i<g[v].size();++i){
            int to=g[v][i];
            int c=cost[v][i];
            if(to==p||to==cs)continue;
            q=max(q,c+di[to]);
        }
        if(max(di[cs]+e,max(q,cp))<=max(di[cs],max(q,cp)+e)){
            return max(di[cs]+e,max(q,cp));
        }
        else{
            return go(cs,v,max(q,cp)+e);
        }
    }
    else{
        return cp;
    }
}
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[]) {
  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);
        z.push_back(go(i,i,0));
        dfs_fill(i,i);
    }
  }
  int sz=-1;
  for(int i=0;i<z.size();++i){
    if(sz==-1||z[sz]<z[i]){
        sz=i;
    }
  }
  if(sz!=0)
  swap(z[0],z[sz]);
  int x=0;
  for(int i=1;i<z.size();++i){
    x=max(x,L+z[i]);
  }
  return z[0]+x;
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();++i){
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int go(int, int, int)':
dreaming.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();++i){
                 ~^~~~~~~~~~~~
dreaming.cpp:37:22: 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:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();++i){
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<z.size();++i){
               ~^~~~~~~~~
dreaming.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<z.size();++i){
               ~^~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 10072 KB Output is correct
2 Incorrect 64 ms 10200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -