Submission #888200

#	Time	Username	Problem	Language	Result	Execution time	Memory
888200		stefanneagu	Roadside Advertisements (NOI17_roadsideadverts)	C++17	30 / 100	59 ms	8148 KiB

roadsideadverts

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 1;

struct str_nod {
  int i, val;
};

vector<vector<str_nod>> adj;
vector<int> no;

int lc[nmax], sz[nmax];

void dfs(int nod, int tata, int cnt) {
  lc[nod] = cnt;
  for(auto it : adj[nod]) {
    if(it.i != tata) {
      no.push_back(it.val);
      dfs(it.i, nod, cnt + 1);
    }
  }
}

int main() {
  //ifstream cin("permsort2.in");
  //ofstream cout("permsort2.out");

  int n;
  cin >> n;
  adj.resize(n + 1);
  for(int i = 1; i < n; i ++) {
    int a, b, c;
    cin >> a >> b  >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
    sz[a] ++;
    sz[b] ++;
  }
  for(int i = 1; i <= n; i ++) {
    if(sz[i] == 1) {
      dfs(i, 0, 0);
      break;
    }
  }
  for(int i = 1; i < n - 1; i ++) {
    no[i] += no[i - 1];
  }
  int q;
  cin >> q;
  for(int i = 1; i <= q; i ++) {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int st_poz = min({lc[a], lc[b], lc[c], lc[d], lc[e]});
    int en_poz = max({lc[a], lc[b], lc[c], lc[d], lc[e]});
    int ans = no[en_poz - 1];
    if(st_poz != 0) {
      ans -= no[st_poz - 1];
    }
    cout << ans << '\n';
  }
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30