oj.uz

답안 #322131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
322131 2020-11-14T06:38:25 Z Sparky_09 Roadside Advertisements (NOI17_roadsideadverts) C++17
0 / 100
 14 ms 10860 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n, l;
const int N = (int)1e5+5;
vector<int> graph[N], gdist[N], d(N), tin, tout;
int timer;
vector<vector<int>> up;

void dfs(int v, int p){
  tin[v] = ++timer;
  up[v][0] = p;
  for(int i = 1; i <= l; i++){
    up[v][i] = up[up[v][i-1]][i-1];
  }
  for(int i = 0; i < gdist[v].size(); i++){
    int loc = graph[v][i];
    if(loc==p) continue;
    d[loc]=d[v]+gdist[v][i];
    dfs(loc,v);
  }
  tout[v] = ++timer;
}

bool is_ancestor(int u, int v){
  return tin[u]<=tin[v] and tout[u]>=tout[v];
}

int lca(int u, int v){
  if(is_ancestor(u,v)) return u;
  if(is_ancestor(v,u)) return v;
  for(int i = l; i >= 0; --i){
    if(!is_ancestor(up[u][i], v)) u = up[u][i];
  }
  return up[u][0];
}

bool fun(int x, int y){
  return tin[x] < tin[y];
}

int dist(int x, int y){
  return d[x] + d[y] - 2 * d[lca(x, y)];
}
             
int main(){
  ios_base::sync_with_stdio(false);
  freopen("input.txt", "r", stdin);
  cin >> n;
  for(int i = 0; i < n-1; i++){
    int x,y,d; cin>>x>>y>>d;
    graph[x].emplace_back(y); 
    graph[y].push_back(x);
    gdist[x].emplace_back(d); 
    gdist[y].push_back(d);
  }

  //preprocess
  tin.resize(n);
  tout.resize(n);
  timer = 0; 
  l = ceil(log2(n));
  up.assign(n, vector<int>(l+1));
  dfs(0,0);

  int quer;
  cin>>quer;
  while(quer--){
    vector<int> q(5);
    for(int& i: q) cin >> i;
    sort(q.begin(), q.end(), fun);
    int ans = 0;
    ans += dist(q[0], lca(0, q[0]));
    for(int i = 1; i < 5; i++){
      ans += dist(lca(q[i-1],q[i]), q[i]);
    }
    //ans += 50;
    cout << ans << '\n';
  }
}

Compilation message

roadsideadverts.cpp: In function 'void dfs(int, int)':
roadsideadverts.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int i = 0; i < gdist[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   49 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 10860 KB Execution killed with signal 6 (could be triggered by violating memory limits)

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 10860 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 10860 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 10860 KB Execution killed with signal 6 (could be triggered by violating memory limits)