oj.uz

Submission #1007376

# Submission time Handle Problem Language Result Execution time Memory
1007376 2024-06-24T17:35:29 Z AdamGS Designated Cities (JOI19_designated_cities) C++17
16 / 100
 300 ms 42836 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, dp[LIM], dp_up[LIM], oc[LIM];
void DFS(int x, int o) {
  for(auto i : V[x]) if(i.st==o) oc[x]=i.nd; else DFS(i.st, x);
  sum+=oc[x];
}
void DFS2(int x, int o) {
  for(auto i : V[x]) if(i.st!=o) {
    DFS2(i.st, x);
    dp[x]=max(dp[x], dp[i.st]+i.nd);
  }
}
void DFS3(int x, int o) {
  pair<ll,ll>ma={-1, -1};
  for(auto i : V[x]) if(i.st!=o) {
    ma=max(ma, {dp[i.st]+i.nd, i.st});
  }
  for(auto i : V[x]) if(i.st!=o) {
    dp_up[i.st]=max(dp_up[i.st], dp_up[x]+oc[i.st]);
    if(i.st!=ma.nd) {
      dp_up[i.st]=max(dp_up[i.st], ma.st+oc[i.st]);
    } else {
      for(auto j : V[x]) if(j.st!=o && j.st!=ma.nd) {
        dp_up[i.st]=max(dp_up[i.st], dp[j.st]+j.nd+oc[i.st]);
      }
    }
  }
  for(auto i : V[x]) if(i.st!=o) DFS3(i.st, x);
}
void DFS4(int x, int o) {
  for(auto i : V[x]) if(i.st==o) sum-=i.nd;
  wynik[1]=max(wynik[1], sum);
  wynik[2]=max(wynik[2], sum+max(dp[x], dp_up[x]));
  for(auto i : V[x]) if(i.st!=o) {
    sum+=i.nd;
    DFS4(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);
  DFS3(0, 0);
  DFS4(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 Correct 1 ms 7000 KB Output is correct
2 Incorrect 2 ms 7004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 210 ms 21400 KB Output is correct
3 Correct 300 ms 34388 KB Output is correct
4 Correct 228 ms 21548 KB Output is correct
5 Correct 177 ms 21444 KB Output is correct
6 Correct 238 ms 23632 KB Output is correct
7 Correct 155 ms 20928 KB Output is correct
8 Correct 205 ms 34904 KB Output is correct
9 Correct 83 ms 19544 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 195 ms 27968 KB Output is correct
3 Correct 257 ms 42836 KB Output is correct
4 Correct 118 ms 26420 KB Output is correct
5 Correct 138 ms 27808 KB Output is correct
6 Correct 192 ms 30108 KB Output is correct
7 Correct 88 ms 27836 KB Output is correct
8 Correct 168 ms 36512 KB Output is correct
9 Correct 83 ms 25528 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Incorrect 2 ms 7004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7004 KB Output is correct
2 Correct 210 ms 21400 KB Output is correct
3 Correct 300 ms 34388 KB Output is correct
4 Correct 228 ms 21548 KB Output is correct
5 Correct 177 ms 21444 KB Output is correct
6 Correct 238 ms 23632 KB Output is correct
7 Correct 155 ms 20928 KB Output is correct
8 Correct 205 ms 34904 KB Output is correct
9 Correct 83 ms 19544 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 195 ms 27968 KB Output is correct
12 Correct 257 ms 42836 KB Output is correct
13 Correct 118 ms 26420 KB Output is correct
14 Correct 138 ms 27808 KB Output is correct
15 Correct 192 ms 30108 KB Output is correct
16 Correct 88 ms 27836 KB Output is correct
17 Correct 168 ms 36512 KB Output is correct
18 Correct 83 ms 25528 KB Output is correct
19 Correct 1 ms 7004 KB Output is correct
20 Incorrect 165 ms 27952 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Incorrect 2 ms 7004 KB Output isn't correct
3 Halted 0 ms 0 KB -