oj.uz

Submission #888200

# Submission time Handle Problem Language Result Execution time Memory
888200 2023-12-16T10:43:00 Z stefanneagu Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 59 ms 8148 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8144 KB Output is correct
2 Correct 59 ms 8144 KB Output is correct
3 Correct 57 ms 8056 KB Output is correct
4 Correct 56 ms 8120 KB Output is correct
5 Correct 57 ms 8148 KB Output is correct
6 Correct 57 ms 8148 KB Output is correct
7 Correct 58 ms 7980 KB Output is correct
8 Correct 57 ms 7952 KB Output is correct
9 Correct 57 ms 8144 KB Output is correct
10 Correct 57 ms 8008 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 56 ms 8144 KB Output is correct
3 Correct 59 ms 8144 KB Output is correct
4 Correct 57 ms 8056 KB Output is correct
5 Correct 56 ms 8120 KB Output is correct
6 Correct 57 ms 8148 KB Output is correct
7 Correct 57 ms 8148 KB Output is correct
8 Correct 58 ms 7980 KB Output is correct
9 Correct 57 ms 7952 KB Output is correct
10 Correct 57 ms 8144 KB Output is correct
11 Correct 57 ms 8008 KB Output is correct
12 Incorrect 35 ms 4944 KB Output isn't correct
13 Halted 0 ms 0 KB -