Submission #1087117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087117		kustizus	Two Currencies (JOI23_currencies)	C++17	40 / 100	2662 ms	80824 KiB

currencies

// #pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define 
#define int long long
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define file "file"
#define __lcm(a, b) a * b / __gcd(a, b)
#define R(x) {cout << x << "\n"; return;}
#define coutf(x) cout << fixed << setprecision(x) 
#define inter(a) cout << a << "\n"; fflush(stdout)

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
// declare
const int N = 1e5;
vector <pair<int,int>> qu[N + 5];
vector <int> ord,g[N + 5], edge[N + 5];
int n, m, q, a[N + 5], b[N + 5], s[N + 5], t[N + 5], x[N + 5], y[N + 5], p[N + 5], c[N + 5];
int idx = 0, l[N + 5], r[N + 5], md[N + 5], valbegin[N + 5], parent[N + 5], sliver[N + 5], gold[N + 5];

struct Fenwick_Tree_Update_Range_Get_Point
{
    int FT[N + 5];
    void clear()
    {
        for (int i = 1; i <= N; ++i) FT[i] = 0;
    }
    void Update(int idx, int val)
    {
        for (;idx <= N; idx += idx & (-idx)) FT[idx] += val;
    }
    
    void UpdateRange(int l, int r, int v)
    {
        Update(r + 1, -v);
        Update(l, v);
    }
    int Get(int idx)
    {
        int val = 0;
        for (; idx; idx -= idx & (-idx)) val += FT[idx];
        return val;
    }
} ft1, ft2;

struct Lca_O1{
    vector <int> order;
    int h[N + 5], pos[N + 5], ST[20][N + 5];
    void dfs(int i, int p)
    {
        order.push_back(i);
        pos[i] = order.size();
        for (int j : g[i])
            if (j != p)
            {
                h[j] = h[i] + 1;
                dfs(j, i);
                order.push_back(i);
            }
    }

    int P(int a, int b)
    {
        return h[a] < h[b] ? a : b;
    }

    void Build()
    {
        int sz = order.size();
        for (int i = 1; i <= sz; ++i) ST[0][i] = order[i - 1];
        for (int i = 1; i < 18; ++i)
            if ((1 << i) <= sz)
            {
                for (int j = 1; j <= sz - (1 << i) + 1; ++j)
                    ST[i][j] = P(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
            }
    }

    int lca(int l, int r)
    {
        l = pos[l], r = pos[r];
        if (l > r) swap(l, r);
        int bit = __lg(r - l + 1);
        return P(ST[bit][l], ST[bit][r - (1 << bit) + 1]);
    }
    // declare h[1]
} lc;

void dfs(int i, int p)
{
    for (pair <int,int> nw : qu[i])
    {
        int v = nw.first, pos = nw.second;
        if (md[pos] < ord[1])
        {
            sliver[pos] = 0;
            gold[pos] += v * ft1.Get(idx);
            continue;
        }
        int l = 1, r = ord.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (ord[mid + 1] <= md[pos]) l = mid + 1;
            else r = mid;
        }
        sliver[pos] += v * ft2.Get(l);
        // if (pos == 1 && md[1] == 8) cout << i << ' ' << v * ft2.Get(l) << ' ' << sliver[pos] << "\n";
        gold[pos] += v * (ft1.Get(idx) - ft1.Get(l));
    }
    for (int j : g[i])
        if (j != p)
        {
            for (int v : edge[j])
            {
                ft1.UpdateRange(v, idx, 1);
                ft2.UpdateRange(v, idx, valbegin[v]);
            }
            dfs(j, i);
            for (int v : edge[j])
            {
                ft1.UpdateRange(v, idx, -1);
                ft2.UpdateRange(v, idx, -valbegin[v]);
            }
        }
}

void Solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i)
    {
        cin >> a[i] >> b[i];
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    lc.dfs(1, 0);
    lc.Build();
    map <int,bool> mp;
    map <int,int> cnt;
    for (int i = 1; i <= m; ++i)
    {
        cin >> p[i] >> c[i];
        mp[c[i]] = true;
    }
    ord.push_back(0);
    for (pair <int, bool> x : mp)
    {
        ord.push_back(x.first);
        cnt[x.first] = ++idx;
        valbegin[idx] = x.first;
    }
    for (int i = 1; i <= m; ++i)
    {
        int u = a[p[i]], v = b[p[i]];
        if (lc.h[u] < lc.h[v]) swap(u, v);
        edge[u].push_back(cnt[c[i]]);
    }
    // for (int i = 1; i <= n; ++i)
    // {
    //     cout << i << ": ";
    //     for (int x : edge[i]) cout << x << " ";
    //     cout << "\n";
    // }
    for (int i = 1; i <= q; ++i)
    {
        cin >> s[i] >> t[i] >> x[i] >> y[i];
        parent[i] = lc.lca(s[i], t[i]);
        l[i] = 0, r[i] = 1e9;
    }
    while (true)
    {
        bool ok = true;
        for (int i = 1; i <= n; ++i) qu[i].clear();
        for (int i = 1; i <= q; ++i)
            if (l[i] != r[i])
            {
                ok = false;
                sliver[i] = gold[i] = 0;
                md[i] = l[i] + r[i] >> 1;
                ++md[i];   
                qu[s[i]].push_back({1, i});  
                qu[t[i]].push_back({1, i});  
                qu[parent[i]].push_back({-2, i});
            }
        if (ok) break;
        dfs(1, 0);
        for (int i = 1; i <= q; ++i)
            if (l[i] != r[i])
            {
                if (sliver[i] > y[i]) r[i] = md[i] - 1;
                else l[i] = md[i];
            }
    }
    for (int i = 1; i <= q; ++i)
    {
        sliver[i] = gold[i] = 0;
        md[i] = l[i];
        qu[s[i]].push_back({1, i});  
        qu[t[i]].push_back({1, i});  
        qu[parent[i]].push_back({-2, i});
    }
    dfs(1, 0);
    // for (int i = 1; i <= q; ++i) cout << l[i] << ' ' << sliver[i] << ' ' << gold[i] << "\n";
    for (int i = 1; i <= q; ++i)
    {
        int d = (y[i] - sliver[i]) / (l[i] + 1);
        if (!gold[i]) d = 0;
        gold[i] = x[i] - gold[i];
        gold[i] += d;
        if (gold[i] < 0) gold[i] = -1;
        cout << gold[i] << "\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen(file ".inp", "r"))
    {
        freopen (file ".inp", "r", stdin);
        freopen (file ".out", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) 
        Solve();
    cerr << "\nTIME: " << 1000 * clock() / CLOCKS_PER_SEC << "ms.";
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:106:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |             int mid = l + r >> 1;
      |                       ~~^~~
currencies.cpp: In function 'void Solve()':
currencies.cpp:183:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  183 |                 md[i] = l[i] + r[i] >> 1;
      |                         ~~~~~^~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:225:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |         freopen (file ".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:226:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |         freopen (file ".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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