oj.uz

Submission #313007

# Submission time Handle Problem Language Result Execution time Memory
313007 2020-10-14T23:33:15 Z VROOM_VARUN Designated Cities (JOI19_designated_cities) C++14
100 / 100
 439 ms 38904 KB 
/*
ID: varunra2
LANG: C++
TASK: descit
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define int long long
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, q;
vector<vector<pair<int, PII>>> adj;
//.x -> city
//.y.x -> cost to go to city
//.y.y -> cost to come here from city
VI ret;
VI delt;
VI deg;
vector<bool> vis;

void init() {
  adj.resize(n + 2);
  ret.assign(n + 2, 0);
  delt.resize(n + 2);
  vis.assign(n, false);
  deg.assign(n + 2, 0);
}

// gets how much mr. k pays from pocket if he only chooses city 0
int dfs1(int u, int v) {
  int ret = 0;
  for (auto& x : adj[u]) {
    if (x.x == v) continue;
    ret += (x.y.x + dfs1(x.x, u));
  }
  return ret;
}

// how much change each node will have if they are selected instead of city 0
void dfs2(int u, int v) {
  for (auto& x : adj[u]) {
    if (x.x == v) continue;
    delt[x.x] = delt[u] + x.y.y - x.y.x;
    dfs2(x.x, u);
  }
}

void gen1() {
  // here we will calculate ret[1]
  int tot = dfs1(0, -1);
  dfs2(0, -1);
  ret[1] = tot + *min_element(all(delt));
}

PII genPar(int u) {
  for (auto& x : adj[u]) {
    if (!vis[x.x]) return MP(x.y.y, x.x);
  }
  return MP(-1, -1);
}

void gen2() {
  // here we calculate ret[2 ... # of leafs - 1]
  // ret[(# of leafs) ... n] = 0

  priority_queue<PII, VII, greater<PII>> pq;

  for (int i = 0; i < n; i++) {
    if (deg[i] == 1) {
      pq.push(MP(genPar(i).x, i));
    }
  }

  // we only have leaf nodes

  while (sz(pq) > 2) {
    int u = pq.top().y;
    int cost = pq.top().x;

    pq.pop();

    vis[u] = true;
    int par = genPar(u).y;
    deg[par]--;

    if (deg[par] == 1) {
      pq.push(MP(genPar(par).x + cost, par));
    } else {
      ret[sz(pq)] = ret[sz(pq) + 1] + cost;
    }
  }
}

int32_t main() {
  // #ifndef ONLINE_JUDGE
  // freopen("descit.in", "r", stdin);
  // freopen("descit.out", "w", stdout);
  // #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  init();

  for (int i = 0; i < n - 1; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--, b--;
    adj[a].PB(MP(b, MP(c, d)));
    adj[b].PB(MP(a, MP(d, c)));
    deg[a]++;
    deg[b]++;
  }

  gen1();
  gen2();

  cin >> q;

  while (q--) {
    int u;
    cin >> u;
    cout << ret[u] << '\n';
  }

  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 389 ms 25072 KB Output is correct
3 Correct 321 ms 36956 KB Output is correct
4 Correct 382 ms 30064 KB Output is correct
5 Correct 385 ms 32304 KB Output is correct
6 Correct 384 ms 32752 KB Output is correct
7 Correct 346 ms 32328 KB Output is correct
8 Correct 330 ms 37752 KB Output is correct
9 Correct 272 ms 34592 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 387 ms 25072 KB Output is correct
3 Correct 334 ms 38264 KB Output is correct
4 Correct 378 ms 30064 KB Output is correct
5 Correct 393 ms 32176 KB Output is correct
6 Correct 388 ms 32880 KB Output is correct
7 Correct 293 ms 34244 KB Output is correct
8 Correct 359 ms 35696 KB Output is correct
9 Correct 273 ms 34352 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 2 ms 640 KB Output is correct
18 Correct 3 ms 768 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 3 ms 768 KB Output is correct
21 Correct 3 ms 640 KB Output is correct
22 Correct 3 ms 640 KB Output is correct
23 Correct 3 ms 640 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 3 ms 768 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 389 ms 25072 KB Output is correct
3 Correct 321 ms 36956 KB Output is correct
4 Correct 382 ms 30064 KB Output is correct
5 Correct 385 ms 32304 KB Output is correct
6 Correct 384 ms 32752 KB Output is correct
7 Correct 346 ms 32328 KB Output is correct
8 Correct 330 ms 37752 KB Output is correct
9 Correct 272 ms 34592 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 387 ms 25072 KB Output is correct
12 Correct 334 ms 38264 KB Output is correct
13 Correct 378 ms 30064 KB Output is correct
14 Correct 393 ms 32176 KB Output is correct
15 Correct 388 ms 32880 KB Output is correct
16 Correct 293 ms 34244 KB Output is correct
17 Correct 359 ms 35696 KB Output is correct
18 Correct 273 ms 34352 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 405 ms 31384 KB Output is correct
21 Correct 320 ms 38392 KB Output is correct
22 Correct 370 ms 30064 KB Output is correct
23 Correct 391 ms 31728 KB Output is correct
24 Correct 387 ms 30684 KB Output is correct
25 Correct 395 ms 31724 KB Output is correct
26 Correct 391 ms 30604 KB Output is correct
27 Correct 386 ms 31788 KB Output is correct
28 Correct 383 ms 32752 KB Output is correct
29 Correct 396 ms 32024 KB Output is correct
30 Correct 376 ms 31020 KB Output is correct
31 Correct 333 ms 34088 KB Output is correct
32 Correct 350 ms 36080 KB Output is correct
33 Correct 275 ms 34588 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 389 ms 25072 KB Output is correct
14 Correct 321 ms 36956 KB Output is correct
15 Correct 382 ms 30064 KB Output is correct
16 Correct 385 ms 32304 KB Output is correct
17 Correct 384 ms 32752 KB Output is correct
18 Correct 346 ms 32328 KB Output is correct
19 Correct 330 ms 37752 KB Output is correct
20 Correct 272 ms 34592 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 387 ms 25072 KB Output is correct
23 Correct 334 ms 38264 KB Output is correct
24 Correct 378 ms 30064 KB Output is correct
25 Correct 393 ms 32176 KB Output is correct
26 Correct 388 ms 32880 KB Output is correct
27 Correct 293 ms 34244 KB Output is correct
28 Correct 359 ms 35696 KB Output is correct
29 Correct 273 ms 34352 KB Output is correct
30 Correct 0 ms 384 KB Output is correct
31 Correct 3 ms 640 KB Output is correct
32 Correct 3 ms 640 KB Output is correct
33 Correct 3 ms 640 KB Output is correct
34 Correct 3 ms 632 KB Output is correct
35 Correct 2 ms 640 KB Output is correct
36 Correct 3 ms 768 KB Output is correct
37 Correct 3 ms 640 KB Output is correct
38 Correct 3 ms 768 KB Output is correct
39 Correct 3 ms 640 KB Output is correct
40 Correct 3 ms 640 KB Output is correct
41 Correct 3 ms 640 KB Output is correct
42 Correct 2 ms 768 KB Output is correct
43 Correct 2 ms 768 KB Output is correct
44 Correct 3 ms 768 KB Output is correct
45 Correct 1 ms 384 KB Output is correct
46 Correct 405 ms 31384 KB Output is correct
47 Correct 320 ms 38392 KB Output is correct
48 Correct 370 ms 30064 KB Output is correct
49 Correct 391 ms 31728 KB Output is correct
50 Correct 387 ms 30684 KB Output is correct
51 Correct 395 ms 31724 KB Output is correct
52 Correct 391 ms 30604 KB Output is correct
53 Correct 386 ms 31788 KB Output is correct
54 Correct 383 ms 32752 KB Output is correct
55 Correct 396 ms 32024 KB Output is correct
56 Correct 376 ms 31020 KB Output is correct
57 Correct 333 ms 34088 KB Output is correct
58 Correct 350 ms 36080 KB Output is correct
59 Correct 275 ms 34588 KB Output is correct
60 Correct 0 ms 384 KB Output is correct
61 Correct 434 ms 32004 KB Output is correct
62 Correct 359 ms 38904 KB Output is correct
63 Correct 420 ms 30700 KB Output is correct
64 Correct 439 ms 32368 KB Output is correct
65 Correct 421 ms 30956 KB Output is correct
66 Correct 439 ms 32376 KB Output is correct
67 Correct 434 ms 31060 KB Output is correct
68 Correct 435 ms 32552 KB Output is correct
69 Correct 426 ms 33256 KB Output is correct
70 Correct 428 ms 32600 KB Output is correct
71 Correct 413 ms 32132 KB Output is correct
72 Correct 383 ms 34340 KB Output is correct
73 Correct 389 ms 36888 KB Output is correct
74 Correct 315 ms 35552 KB Output is correct