제출 #49302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49302		doowey	꿈 (IOI13_dreaming)	C++14	18 / 100	86 ms	12696 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 9;
vector<pii>E[N];

vector<int>comp[N];
bool vis[N];
int p = 0;

void Split(int u){
  if(vis[u] == true)
    return;
  comp[p].push_back(u);
  vis[u] = true;
  for(auto x : E[u]){
    if(!vis[x.fi])  
      Split(x.fi);
  }
}

int dim[N];
int hf[N];

int dist[N];
int las[N];

void search(int x){ // component x
  int st = comp[x][0];
  for(int i = 0;i < comp[x].size();i ++ ){
    dist[comp[x][i]] = (int)2e9 + 9;
  }
  dist[st] = 0;
  queue<int>ii;
  ii.push(st);
  int cr;
  while(!ii.empty()){
    cr = ii.front();
    ii.pop();
    for(int i = 0;i < E[cr].size();i ++ ){
      if(dist[E[cr][i].fi] > dist[cr] + E[cr][i].se){
        dist[E[cr][i].fi] = dist[cr] + E[cr][i].se;
        ii.push(E[cr][i].fi);
      }
    }
  }
  int mx = -1;
  int z = 0;
  for(auto y : comp[x]){
    if(dist[y] > mx){
      mx = dist[y];
      z = y;
    }
    dist[y] = (int)2e9 + 9;
    las[y] = -1;
  }
  ii.push(z);
  dist[z] = 0;
  while(!ii.empty()){
    cr = ii.front();
    ii.pop();
    for(auto x : E[cr]){
      if(dist[cr] + x.se < dist[x.fi]){
        las[x.fi] = cr;
        dist[x.fi] = dist[cr] + x.se;
        ii.push(x.fi);
      }
    }
  }
  mx = -1;
  z = 0;
  for(auto y : comp[x]){
    if(dist[y] > mx){
      mx = dist[y];
      z = y;
    }
  }
  dim[x] = mx;
  hf[x] = dist[z];
  while(las[z] != -1 and dist[z] * 2 > mx){
    hf[x] = min(hf[x],max(dist[z],mx - dist[z]));
    z = las[z];
  }
}

int travelTime(int n, int m, int len, int fr[], int to[], int tt[]) {
  for(int i = 0;i < m; i ++ ){
    E[fr[i]].push_back(mp(to[i], tt[i]));
    E[to[i]].push_back(mp(fr[i], tt[i]));
  }
  for(int i = 0;i < n;i ++ )
    if(!vis[i]){
      Split(i);
      p ++ ;
    }
  for(int j = 0;j < p;j ++ )
    search(j);
  if(p == 1)
    return dim[0];
  if(p == 2)
    return max(max(dim[0], dim[1]), hf[0] + hf[1] + len); 
  sort(hf, hf + p);
  int ans = 0;
  for(int i = 0;i < p;i ++ )
    ans = max(ans, dim[i]);
  int tri;
  int sum;
  int cnt;
  int mx;
  int mz = (int)2e9 + 9;
  for(int i = 0;i < p;i ++ ){
    tri = 0;
    sum = 0;
    cnt = 0;
    mx = 0;
    for(int j = p - 1;j >= 0;j -- ){
      if(j != i){
        sum += hf[j];
        cnt++;
        if(cnt == 1){
          mx = hf[j];
        }
      }
      if(cnt == 2)
        break;
    }
    tri = max(tri, mx + len + hf[i]);
    tri = max(tri, sum + len + len);
    mz = min(mz, tri);
  }
  ans = max(ans , mz);
  return ans;
}

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

dreaming.cpp: In function 'void search(int)':
dreaming.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i < comp[x].size();i ++ ){
                 ~~^~~~~~~~~~~~~~~~
dreaming.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < E[cr].size();i ++ ){
                   ~~^~~~~~~~~~~~~~

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