oj.uz

Submission #107401

# Submission time Handle Problem Language Result Execution time Memory
107401 2019-04-24T05:23:09 Z shoemakerjo Designated Cities (JOI19_designated_cities) C++14
7 / 100
 451 ms 34808 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int maxn = 200010;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, pll>
#define mp make_pair

int n, q;

ll seg[maxn*4]; //a max seg tree

//we want the seg-tree to go in euler tour order
int qus[maxn];
vector<pil> adj[maxn];

ll ans[maxn]; //store ans for each value
ll dep[maxn]; //distance from root to me
int par[maxn];
ll plink[maxn];

int rt; //some global root variable
ll esum = 0LL; //total edge sum
//barebones dfs
void dfs(int u, int p = -1) {
  if (p == -1) {
    dep[u] = 0LL;
    par[u] = -1;
  }
  for (pil vp : adj[u]) {
    if (vp.first == p) continue;
    dep[vp.first] = dep[u] + vp.second.first;
    par[vp.first] = u;
    plink[vp.first] = vp.second.second;
    dfs(vp.first, u);
  }
}

void dfs1(int u, ll msum = 0LL) {
  ans[1] = min(ans[1], esum - msum);
  for (pil vp : adj[u]) {
    if (vp.first != par[u]) {
      dfs1(vp.first, msum - vp.second.second +
        vp.second.first);
    }
  }
}

void go1() {
  //finds the answer for 1 by itself
  //when I go to a child, I reverse that edge
  //start with all going down
  ans[1] = esum;
  ll csum = 0LL;
  for (int i = 1; i <= n; i++) {
    if (i != rt) csum += plink[i];
  }
  dfs1(rt, csum);
}

pii go2() {
  return {-1, -1};
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  int a, b;
  ll c, d;
  for (int i = 0; i < n-1; i++) {
    cin >> a >> b >> c >> d;
    adj[a].emplace_back(b, mp(c, d));
    adj[b].emplace_back(a, mp(d, c));
    esum += c;
    esum += d;
  }
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> qus[i];
  }
  if (n == 2) {
    //just bash
    for (int i = 1; i <= q; i++) {
      if (qus[i] == 2) {
        cout << 0 << endl;
      }
      else {
        cout << min(adj[1][0].second.first,
          adj[1][0].second.second);
      }
    }
    return 0;
  }

  //now we want to root at a non-leaf
  rt = 1;
  for (int i = 2; i <= n; i++) {
    if (adj[i].size() != 1) rt = i;
  }
  dfs(rt);

  go1();
  pii vp = go2();

  //now we are just printing out answer (for now - 1/2)
  for (int i = 1; i <= q; i++) {
    cout << ans[qus[i]] << '\n';
  }
  cout.flush();
}

//calculate the answer for one
//use a dp to calculate the answer for two (root at non-leaf)
//greedily add nodes until we get to each val (if none left - do nothing)

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:107:7: warning: variable 'vp' set but not used [-Wunused-but-set-variable]
   pii vp = go2();
       ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 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 6 ms 4992 KB Output is correct
2 Correct 360 ms 28352 KB Output is correct
3 Correct 410 ms 33624 KB Output is correct
4 Correct 332 ms 27000 KB Output is correct
5 Correct 308 ms 28072 KB Output is correct
6 Correct 347 ms 29612 KB Output is correct
7 Correct 316 ms 27300 KB Output is correct
8 Correct 451 ms 34808 KB Output is correct
9 Correct 228 ms 26344 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Incorrect 371 ms 28404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 360 ms 28352 KB Output is correct
3 Correct 410 ms 33624 KB Output is correct
4 Correct 332 ms 27000 KB Output is correct
5 Correct 308 ms 28072 KB Output is correct
6 Correct 347 ms 29612 KB Output is correct
7 Correct 316 ms 27300 KB Output is correct
8 Correct 451 ms 34808 KB Output is correct
9 Correct 228 ms 26344 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Incorrect 371 ms 28404 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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