제출 #986202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986202		proteam23	Two Currencies (JOI23_currencies)	C++14	100 / 100	2560 ms	49652 KiB

currencies

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define getbit(x,y) (((x)>>(y))&1)
#define turnon(x,y) ((x)|(1<<y))
#define turnof(x,y) ((x)^(1<<y))
#define oo 1000000000000000000
#define pb push_back
#define all(x) x.begin(),x.end()
#define con(mask) mask=(mask-1)&mask
#define Unique(val) val.erase(unique(val.begin(),val.end()),val.end())

const int mod = 1e9 + 7;
const int base = 1e9;
using namespace std;

vector<int>e[100005];
int cnt_silver[100005], cnt_gold[100005];


int n, q, m;
struct nhan {
    int u, v, gold, silver;

    nhan (int _u = 0, int _v = 0, int _gold = 0, int _silver = 0) {
        u = _u;
        v = _v;
        gold = _gold;
        silver = _silver;
    }
} h[100005];

int L[100005], R[100005];
ii Edge[100005];

vector<ii>a;

int f[100005][17];
int hi[100005];
int tin[100005], tout[100005], cnt;

void dfs(int u, int p) {
    tin[u] = ++cnt;
    for(int i = 0; i < e[u].size(); i++) {
        int v = e[u][i];
        if(v != p) {
            hi[v] = hi[u] + 1;
            f[v][0] = u;
            dfs(v, u);
        }
    }
    tout[u] = cnt;
}

int lca(int u, int v) {
    if(hi[u] > hi[v]) swap(u, v);

    for(int i = 16; i >= 0; i--) {
        if(hi[f[v][i]] >= hi[u]) {
            v = f[v][i];
        }
    }

    if(u == v) return u;

    for(int i = 16; i >= 0; i--) {
        if(f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

int bit[100005];
int bit_canh[100005];
void update(int a[], int pos, int val) {
    for(int i = pos; i <= n; i += i&-i) {
        a[i] += val;
    }
}
int get(int a[], int pos) {
    int ans = 0;
    for(int i = pos; i >= 1; i -= i&-i) {
        ans += a[i];
    }
    return ans;
}
int need[100005];

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

    cin >> n >> m >> q;

    for(int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v;
        e[u].pb(v);
        e[v].pb(u);
        Edge[i] = make_pair(u, v);
    }

    hi[1] = 1;
    dfs(1, 1);

    for(int j = 1; j < 17; j++) {
        for(int i = 1; i <= n; i++) {
            if(f[i][j - 1]) {
                f[i][j] = f[f[i][j - 1]][j - 1];
            }
        }
    }

    for(int i = 1; i <= m; i++) {
        int x, y;
        cin >> x;
        cin >> y;
        a.pb(make_pair(y, x));
    }

    a.pb(make_pair(-1, -1));

    for(int i = 1; i <= q; i++) {
        cin >> h[i].u >> h[i].v >> h[i].gold >> h[i].silver;
        L[i] = 0;
        R[i] = m;
    }

    sort(all(a));

    while(1) {
        vector<ii>b;

        for(int i = 1; i <= n; i++) bit[i] = 0, bit_canh[i] = 0;

        for(int i = 1; i <= q; i++) {
            if(L[i] <= R[i]) b.pb(make_pair((L[i] + R[i]) / 2, i));
        }

        if(b.size() == 0) break;

        sort(all(b));

        int pos = 1;

        for(int i = 0; i < b.size(); i++) {
            while(pos <= m && pos <= b[i].fi) {

                int vt = a[pos].se;

                int u = Edge[a[pos].se].fi;
                int v = Edge[a[pos].se].se;

                if(hi[u] > hi[v]) swap(u, v);

                update(bit, tin[v], a[pos].fi);
                update(bit_canh, tin[v], 1);
                update(bit, tout[v] + 1, -a[pos].fi);
                update(bit_canh, tout[v] + 1, -1);

                pos++;
            }

            int vt = b[i].se;
            int sum = get(bit, tin[h[vt].u]) + get(bit, tin[h[vt].v]) - 2 * get(bit, tin[lca(h[vt].u, h[vt].v)]);
            int canh = get(bit_canh, tin[h[vt].u]) + get(bit_canh, tin[h[vt].v]) - 2 * get(bit_canh, tin[lca(h[vt].u, h[vt].v)]);

            if(sum <= h[vt].silver) {
                L[vt] = b[i].fi + 1;
                need[vt] = canh;
            }
            else {
                R[vt] = b[i].fi - 1;
            }
        }
    }

    for(int i = 1; i <= n; i++) bit_canh[i] = 0;

    for(int i = 1; i <= m; i++) {
        int vt = a[i].se;
        int u = Edge[vt].fi;
        int v = Edge[vt].se;
        if(hi[u] > hi[v]) swap(u, v);


        update(bit_canh, tin[v], 1);
        update(bit_canh, tout[v] + 1, -1);
    }

    for(int i = 1; i <= q; i++) {
        int cha = lca(h[i].u, h[i].v);
        int can = get(bit_canh, tin[h[i].u]) + get(bit_canh, tin[h[i].v]) - 2 * get(bit_canh, tin[cha]) - need[i];
        int res = h[i].gold - can;
        if(res < 0) res = -1;
        cout << res << "\n";
    }





}
//      ProTeam
//(¯`·.·´¯) (¯`·.·´¯)
//`·.¸(¯`·.·´¯)¸ .·
//×°× ` ·.¸.·´ ×°×

컴파일 시 표준 에러 (stderr) 메시지

currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < e[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:112:19: warning: unused variable 'w' [-Wunused-variable]
  112 |         int u, v, w;
      |                   ^
currencies.cpp:162:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         for(int i = 0; i < b.size(); i++) {
      |                        ~~^~~~~~~~~~
currencies.cpp:165:21: warning: unused variable 'vt' [-Wunused-variable]
  165 |                 int vt = a[pos].se;
      |                     ^~

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