Submission #1304249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304249		KietJ	Two Currencies (JOI23_currencies)	C++17	0 / 100	2 ms	2880 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;

#define fi first
#define pdi pair < pair < double, double >, int >
#define se second
#define ll long long
#define pii pair < int, int >
const int MOD = 1e9 + 7;
const ll inf = 1e18;

vector < int > g[maxn];
pii edge[maxn];
int n, m, k, W[maxn], up[25][maxn],h[maxn];

void dfs(int u) {
    for (int v : g[u]) {
      if (v == up[0][u]) continue;
      h[v] = h[u] + 1;
      up[0][v] = u;
      for (int j = 1; j <= 20; j++) up[j][v] = up[j - 1][up[j - 1][v]];
      dfs(v);
    }
}

int LCA(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  int k = h[u] - h[v];
  for (int i = 20; i >= 0; i--) {
    if (k >> i & 1) u = up[i][u];
  }

  if (u == v) return u;

  for (int i = 20; i >= 0; i--) {
    if (up[i][u] != up[i][v]) {
      u = up[i][u];
      v = up[i][v];
    }
  }

  return up[0][u];
}

int dist(int u, int v) {
    return h[u] + h[v] - 2 * h[LCA(u, v)];
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);     cout.tie(0);

    #define NAME "test"
    if (fopen(NAME".INP", "r")) {
        freopen(NAME".INP", "r",stdin);
        freopen(NAME".OUT", "w",stdout);
    }

    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        cin >> edge[i].fi >> edge[i].se;
    }

    for (int i = 1; i <= m; i++) {
        int id, val;
        cin >> id >> val;
        int u = edge[i].fi;
        int v = edge[i].se;
        W[id] += val;
    }

    int cst = 0;

    for (int i = 1; i < n; i++) {
        int u = edge[i].fi;
        int v = edge[i].se;
        int w = W[i];
        cst = w;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
    for (int i = 1; i <= k; i++) {
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        int d = dist(u, v);
        int f = d * cst;
        if (y >= f) {
            cout << x << '\n';
        } else {
            int cnt = f / d * cst;
            d -= cnt;
            if (x >= d) cout << x - d << '\n';
            else cout << -1 << '\n';
        }
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen(NAME".INP", "r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(NAME".OUT", "w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32