oj.uz

답안 #49303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49303 2018-05-25T10:57:04 Z doowey 꿈 (IOI13_dreaming) C++14
18 / 100
 83 ms 12660 KB 
#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];
  sort(hf, hf + p);
  if(m == n - 2){
    return max(max(dim[0], dim[1]), hf[0] + hf[1] + len);
  }
  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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12660 KB Output is correct
2 Correct 78 ms 12476 KB Output is correct
3 Correct 50 ms 10996 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 20 ms 6784 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12660 KB Output is correct
2 Correct 78 ms 12476 KB Output is correct
3 Correct 50 ms 10996 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 20 ms 6784 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12660 KB Output is correct
2 Correct 78 ms 12476 KB Output is correct
3 Correct 50 ms 10996 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 20 ms 6784 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 10676 KB Output is correct
2 Correct 59 ms 10616 KB Output is correct
3 Correct 54 ms 10616 KB Output is correct
4 Correct 73 ms 10616 KB Output is correct
5 Correct 54 ms 10616 KB Output is correct
6 Correct 61 ms 11000 KB Output is correct
7 Correct 65 ms 10872 KB Output is correct
8 Correct 50 ms 10488 KB Output is correct
9 Correct 56 ms 10540 KB Output is correct
10 Correct 56 ms 10872 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct
12 Correct 32 ms 9848 KB Output is correct
13 Correct 31 ms 9884 KB Output is correct
14 Correct 35 ms 9848 KB Output is correct
15 Correct 31 ms 9820 KB Output is correct
16 Correct 34 ms 9840 KB Output is correct
17 Correct 29 ms 9872 KB Output is correct
18 Correct 29 ms 9788 KB Output is correct
19 Correct 31 ms 9872 KB Output is correct
20 Correct 6 ms 5120 KB Output is correct
21 Correct 5 ms 4992 KB Output is correct
22 Correct 7 ms 5248 KB Output is correct
23 Correct 30 ms 9848 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12660 KB Output is correct
2 Correct 78 ms 12476 KB Output is correct
3 Correct 50 ms 10996 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 20 ms 6784 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12660 KB Output is correct
2 Correct 78 ms 12476 KB Output is correct
3 Correct 50 ms 10996 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 20 ms 6784 KB Output is correct
7 Incorrect 6 ms 5120 KB Output isn't correct
8 Halted 0 ms 0 KB -