제출 #322545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
322545		lukameladze	꿈 (IOI13_dreaming)	C++14	18 / 100	354 ms	35556 KiB

dreaming

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
long long ww,lv[300005],lv1[300005],mx,vert,fix[300005],x1,x2,x,y;
std::vector <long long> v[300005],vv,ans;
map < pair <long long, long long > , long long > mp; 
void dfs(int a, int p)
{
    fix[a]=1;
     if (ww==1) vv.push_back(a);
     if (p!=-1)
     lv[a]=lv[p]+mp[{a,p}];
     else lv[a]=0;
     if (lv[a]>mx)
     {
          vert=a;
          mx=lv[a];
     }
     for (int i=0; i<v[a].size(); i++) 
     {
          if (v[a][i]!=p)
          {
               dfs(v[a][i],a);
          }
     }
}
void dfs1(int a, int p)
{
     if (p!=-1)
     lv1[a]=lv1[p]+mp[{a,p}];
     else lv1[a]=0;
     for (int i=0; i<v[a].size(); i++)
     {
          if (v[a][i]!=p)
          {
               dfs1(v[a][i],a);
          }
     }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
	for (int i=0; i<=1e5; i++)
	v[i].clear();
	ans.clear();
     for (int i=0; i<M; i++)
     {
          mp[{A[i],B[i]}]=T[i];
          mp[{B[i],A[i]}]=T[i];
          v[A[i]].push_back(B[i]);
          v[B[i]].push_back(A[i]);
     }
 
     for (int i=0; i<N; i++)
     {
            mx=0;
          if (!fix[i])
          {
               vv.clear();
               ww=1;
               dfs(i,-1);
               x1=vert;
               ww=0;
               mx=0;
               dfs(x1,-1);
               x2=vert;
               dfs1(x2,-1);
               x=1e10;
               for (int j=0; j<vv.size(); j++)
               {
                    y=max(lv[vv[j]], lv1[vv[j]]);
                    x=min(x, y);
               }
               ans.push_back(x);
          }
     }
     sort(ans.begin(), ans.end());
     reverse(ans.begin(), ans.end());
     if (ans.size()>=3)
     {
          return max(ans[1]+ans[2]+2*L, ans[0]+ans[1]+L);
     }
     if (ans.size()>=2)
     {
          return ans[0]+ans[1]+L;
     }
     return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |      for (int i=0; i<v[a].size(); i++)
      |                    ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |      for (int i=0; i<v[a].size(); i++)
      |                    ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                for (int j=0; j<vv.size(); j++)
      |                              ~^~~~~~~~~~

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