oj.uz

답안 #792656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792656 2023-07-25T07:53:18 Z vjudge1 Two Currencies (JOI23_currencies) C++17
0 / 100
 1 ms 2644 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct citizen {
    int s, t;
    int x, y;
    int inx;
};

int n, m, q;
vector<pair<int, int>> edges;
vector<pair<int, int>> checkpoints;
vector<citizen> citizens;
vector<int> answers;

namespace Subtask2 {
    const int N = 1e5 + 10;
    vector<int> g[N];
    int tin[N], tout[N], anc[N][17], T;
    bool f[N] = {};
    int cnt[N] = {};
    int C;
    void precalc(int s, int p) {
        tin[s] = T++;
        anc[s][0] = p;
        cnt[s] = cnt[p] + f[s]; 
        for(int i = 1; i < 17; i++) 
            anc[s][i] = anc[anc[s][i - 1]][i - 1];
        for(int to : g[s]) {
            if(to == p) continue;
            precalc(to, s);
        }
        tout[s] = T++;
    }
    bool up(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }
    int lca(int u, int v) {
        if(up(u, v)) return u;
        if(up(v, u)) return v;
        for(int i = 16; i >= 0; i--) {
            if(!up(anc[u][i], v)) u = anc[u][i];
        }
        return anc[u][0];
    }
    void init() {
        for(auto [u, v] : edges) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        precalc(1, 1);
        
        for(auto [p, c] : checkpoints) {
            auto [u, v] = edges[p - 1];
            if(tin[u] > tin[v]) swap(u, v);
            f[v] = true;
            C = c;
        }
        precalc(1, 1);
        
        for(citizen c : citizens) {
            int u = lca(c.s, c.t);
            int k = cnt[c.s] + cnt[c.t] - 2 * cnt[u];
            int ans = c.x - max(k - c.y / C, 0);
            if(ans < 0) ans = -1;
            answers[c.inx] = ans;
            // cout << c.inx << ' ' << ans << '\n';
        }
    } 
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
    }
    for(int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c;
        checkpoints.push_back({p, c});
    }
    for(int i = 0; i < q; i++) {
        citizen s;
        cin >> s.s >> s.t >> s.x >> s.y;
        s.inx = i;
        citizens.push_back(s);
    }
    answers.resize(q);
    Subtask2::init();
    for(int c : answers) 
        cout << c << '\n';
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -