제출 #1256461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256461		Bahamin	Two Currencies (JOI23_currencies)	C++20	100 / 100	1578 ms	38456 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

vector<int> adj[MAX_N];
int st[MAX_N];
int fi[MAX_N];
int timer = 0;
int par[MAX_N][LOG];
int cnt[MAX_N];
int h[MAX_N];

void dfs(int u, int p)
{
    par[u][0] = p;
    st[u] = timer++;
    for (int i = 1; i < LOG; i++) par[u][i] = par[par[u][i - 1]][i - 1];
    for (int v : adj[u]) if (v != p) h[v] = h[u] + 1, dfs(v, u);
    fi[u] = timer;
}

void dfs1(int u, int p)
{
    cnt[u] += cnt[p];
    for (int v : adj[u]) if (v != p) dfs1(v, u);
}

int getpar(int u, int k)
{
    for (int i = 0; i < LOG; i++) if (k & (1 << i)) u = par[u][i];
    return u;
}

int lca(int u, int v)
{
    if (h[u] < h[v]) swap(u, v);
    u = getpar(u, h[u] - h[v]);
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; i--) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}

ll fen[MAX_N];

void add(int x, int y)
{
    x++;
    for (int i = x; i < MAX_N; i += i & (-i)) fen[i] += y;
}

ll get(int x)
{
    x++;
    ll ans = 0;
    for (int i = x; i > 0; i -= i & (-i)) ans += fen[i];
    return ans;
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> edges;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edges.push_back(make_pair(u, v));
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    vector<pair<int, int>> ms;
    for (int i = 0; i < m; i++)
    {
        int p, c;
        cin >> p >> c;
        int a = edges[p - 1].first;
        int b = edges[p - 1].second;
        if (h[a] < h[b]) swap(a, b);
        ms.push_back(make_pair(c, a));
        cnt[a]++;
    }
    dfs1(1, 0);
    sort(all(ms));
    int s[q], t[q];
    ll x[q], y[q];
    int l[q];
    int r[q];
    int ans[q];
    vector<int> qs[m];
    for (int i = 0; i < q; i++) cin >> s[i] >> t[i] >> x[i] >> y[i], qs[(m - 1) >> 1].push_back(i), l[i] = -1, r[i] = m;
    for (int i = 0; i < LOG; i++)
    {
        fill(fen, fen + MAX_N, 0);
        for (int j = 0; j < m; j++) 
        {
            add(st[ms[j].second], ms[j].first);
            add(fi[ms[j].second], -ms[j].first);
            for (int xx : qs[j]) 
            {
                if (get(st[s[xx]]) + get(st[t[xx]]) - 2 * get(st[lca(s[xx], t[xx])]) <= y[xx]) l[xx] = j;
                else r[xx] = j;
            }
            qs[j].clear();
        } 
        for (int j = 0; j < q; j++) if (r[j] - l[j] > 1) qs[(l[j] + r[j]) >> 1].push_back(j);
    }
    for (int i = 0; i < m; i++) qs[i].clear();
    for (int i = 0; i < q; i++) 
    {
        if (l[i] == -1) ans[i] = 0;
        else qs[l[i]].push_back(i);
    }
    fill(fen, fen + MAX_N, 0);
    for (int j = 0; j < m; j++)
    {
        add(st[ms[j].second], 1);
        add(fi[ms[j].second], -1);
        for (int xx : qs[j]) ans[xx] = get(st[s[xx]]) + get(st[t[xx]]) - 2 * get(st[lca(s[xx], t[xx])]);
    }
    for (int i = 0; i < q; i++)
    {
        int num = cnt[s[i]] + cnt[t[i]] - 2 * cnt[lca(s[i], t[i])] - ans[i];
        cout << max((ll) -1, x[i] - num) << "\n";
    }
}   

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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