oj.uz

Submission #1007363

# Submission time Handle Problem Language Result Execution time Memory
1007363 2024-06-24T17:21:39 Z AdamGS Designated Cities (JOI19_designated_cities) C++17
7 / 100
 115 ms 33876 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll wynik[LIM], sum;
void DFS(int x, int o) {
  for(auto i : V[x]) if(i.st==o) sum+=i.nd; else DFS(i.st, x);
}
void DFS2(int x, int o) {
  for(auto i : V[x]) if(i.st==o) sum-=i.nd;
  wynik[1]=max(wynik[1], sum);
  for(auto i : V[x]) if(i.st!=o) {
    sum+=i.nd;
    DFS2(i.st, x);
    sum-=i.nd;
  }
  for(auto i : V[x]) if(i.st==o) sum+=i.nd;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  ll summ=0;
  rep(i, n-1) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d; --a; --b;
    V[a].pb({b, c});
    V[b].pb({a, d});
    summ+=c+d;
  }
  DFS(0, 0);
  DFS2(0, 0);
  rep(i, n+1) wynik[i]=summ-wynik[i];
  int q;
  cin >> q;
  while(q--) {
    int x;
    cin >> x;
    cout << wynik[x] << '\n';
  }
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 102 ms 23120 KB Output is correct
3 Correct 115 ms 33620 KB Output is correct
4 Correct 82 ms 21844 KB Output is correct
5 Correct 82 ms 23220 KB Output is correct
6 Correct 93 ms 24752 KB Output is correct
7 Correct 109 ms 22720 KB Output is correct
8 Correct 110 ms 33876 KB Output is correct
9 Correct 66 ms 22496 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 102 ms 23120 KB Output is correct
3 Correct 115 ms 33620 KB Output is correct
4 Correct 82 ms 21844 KB Output is correct
5 Correct 82 ms 23220 KB Output is correct
6 Correct 93 ms 24752 KB Output is correct
7 Correct 109 ms 22720 KB Output is correct
8 Correct 110 ms 33876 KB Output is correct
9 Correct 66 ms 22496 KB Output is correct
10 Incorrect 2 ms 6492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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