Submission #661292

#	Time	Username	Problem	Language	Result	Execution time	Memory
661292		atigun	Dreaming (IOI13_dreaming)	C++11	Compilation error	0 ms	0 KiB

dreaming

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

using namespace std;
typedef long long ll;

const int maxn = 1e5;
vector<vector<pair<int, int>>> g(maxn+5);
vector<bool> vis(maxn+5, false);
vector<int> dt(maxn+5), ht(maxn+5, 0), group(maxn+5);
vector<multiset<int>> S(maxn+5);

void dfs1(int v, int P){
  group[v] = P;
  vis[v] = 1;
  int maxi1 = 0, maxi2 = 0;
  for(pair<int, int> pp : g[v]){
    int u = pp.first, w = pp.second;
    if(vis[u])
      continue;
    dfs1(u, P);
    ht[v] = max(ht[v], ht[u]+w);
    if(ht[u]+w >= maxi1){
      maxi2 = maxi1, maxi1 = ht[u]+w;
    } else if(ht[u]+w >= maxi2){
      maxi2 = ht[u]+w;
    }
  }
  dt[v] = maxi1+maxi2;
}

void dfs2(int v, int p){
  vis[v] = 1;
  for(pair<int, int> pp : g[v]){
    int u = pp.first, w = pp.second;
    if(u == p)
      continue;
    S[v].insert(ht[u]+w);
  }
  for(pair<int, int> pp : g[v]){
    int u = pp.first, w = pp.second;
    if(u == p)
      continue;
    if(S[v].size() == 1){
      S[u].insert(w);
    } else if(!S[v].empty()){
      S[v].erase(S[v].find(ht[u]+w));
      int best = *--S[v].end();
      S[u].insert(best+w);
      S[v].insert(ht[u]+w);
    }
  }
  if(!S[v].empty())
    ht[v] = *--S[v].end();
  for(pair<int, int> pp : g[v]){
    int u = pp.first;
    if(vis[u])
      continue;
    dfs2(u, v);
  }
}

int travelTime(int N, int M, int L, vector<int>& A, vector<int>& B, vector<int>& T){
  for(int i = 0; i < M; i++){
    g[A[i]].emplace_back(B[i], T[i]);
    g[B[i]].emplace_back(A[i], T[i]);
  }
  for(int i = 0; i < N; i++)
    if(!vis[i])
      dfs1(i, i);
  fill(vis.begin(), vis.end(), false);
  for(int i = 0; i < N; i++)
    if(!vis[i])
      dfs2(i, -1);
  int ans = 0;
  for(int i = 0; i < N; i++)
    ans = max(ans, dt[i]);  
  vector<pair<int, int>> order;
  order.reserve(N);
  for(int i = 0; i < N; i++)
    order.emplace_back(ht[i], group[i]);
  sort(order.begin(), order.end());
  vector<int> G;
  G.reserve(N);
  vector<bool> used(N+5, false);
  for(int i = 0; i < N; i++){
    if(used[order[i].second])
      continue;
    G.emplace_back(order[i].first);
    used[order[i].second] = true;
  }
  int GN = G.size();
  sort(G.begin(), G.end(), [&](int n1, int n2){
    return n1 > n2;
  });
  for(int i = GN-1; i > 0; i--)
    ans = max(ans, G[0] + G[i] + i*L);
  return ans;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cczyGSe1.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status