Submission #912694

#	Time	Username	Problem	Language	Result	Execution time	Memory
912694		Pentagonal	Two Currencies (JOI23_currencies)	C++17	0 / 100	11 ms	27740 KiB

currencies

// #pragma GCC target("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
//#pragma GCC -Wnarrowing

//Template {
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
//IO templates
//Note: use endl only for interactive problems or to debug segfaults; use newl for other problems
#define newl "\n"
#define fastIO ios::sync_with_stdio(false); cin.tie(nullptr)
#define fileIO(x) ifstream fin((str) x + (str) ".in"); ofstream fout((str) x + (str) ".out");
// void fileIO(string x) {}
#define flush() fflush(stdout)
#define interact(n) fflush(stdout); cin >> n; if (n == -1) return 0
#define testcases int tt; cin >> tt; fun (i, tt) solve();

#define edgeIO(m) fun (i, m) {int a, b; cin >> a >> b; addEdges(a, b);}
#define WeightedEdgeIO(m) fun (i, m) {int a, b, c; cin >> a >> b >> c; addWeightedEdges(a, b, c);}
#define numberedEdgeIO(m) fun (i, m) {int a, b; cin >> a >> b; addWeightedEdges(a, b, i);}
//types
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
// #define int long long
#define ld long double
#define str string
#define boolean bool
#define String string
 
//vector
#define pb push_back
#define append push_back
 
//pairs
#define mp make_pair
#define p2 pair<int, int>
#define p3 pair<int, p2>
#define m3(x, y, z) mp(x, mp(y, z))
#define ich first
#define ni second.first
#define sanshi second.second
 
//For loops
#define ahegao(i, a, b) for (int i = a; i < b; i++)
#define baka(i, b, a) for (int i = b; i > a; i--)
#define fun(i, n) for (int i = 1; i <= (n); (i)++)
#define fon(i, n) for (int i = 0; i < (n); (i)++)
#define fur(i, n) for (auto i : (n))
#define oniichan(i, n) for (auto &i : (n))
 
//Sorts
#define sz(aaa) ((signed) aaa.size())
// #define len(aaa) ((signed) aaa.size())
#define all(a) a.begin(), a.end()
#define Sort(a) sort((a).begin(), (a).end())
#define rSort(a) sort((a).rbegin(), (a).rend())
#define clamp(x, y) (x) = min((int) (x), (int) (y))
#define CLAMP(x, y) (x) = max((int) (x), (int) (y))
 
//Other stuff
#define pqueue priority_queue
#define elif else if
#define addEdges(a, b) adj[a].pb(b); adj[b].pb(a)
#define addWeightedEdges(a, b, c) adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c))
// #define find find_by_order
#define printLength(x) if (x < INF) cout << x << newl; else cout << -1 << newl;
// #define printVector(a) fur (i, a) cout << i << ' '; cout << newl;
void printVector(vector<int> DontUseThisName) {
    fur (i, DontUseThisName) cout << i << ' '; cout << newl;
}
void printVector(vector<p2> DontUseThisName) {
    fur (i, DontUseThisName) cout << i.first << ' ' << i.second << newl; cout << newl;
}
void printVector(vector<vector<int>> DontUseThisName) {
    fur (i, DontUseThisName) printVector(i); cout << newl;
}

void pv(int a) {cout << a << newl;}
void pv(int a, int b) {printVector({a, b});}
void pv(p2 a) {printVector({a.first, a.second});};
void pv(int a, int b, int c) {printVector({a, b, c});}
void pv(int a, int b, int c, int d) {printVector({a, b, c, d});}
void pv(int a, int b, int c, int d, int e) {printVector({a, b, c, d, e});}
void pv(int a, int b, int c, int d, int e, int f) {printVector({a, b, c, d, e, f});}
// void pv(int a, )
// void printVector(vector<char> DontUseThisName) {
//     fur (i, DontUseThisName) cout << i << ' '; cout << newl;
// }
// void printRange(vector<int>::iterator Left, vector<int>::iterator Right) {
//     for (auto i = Left; i < Right; i++) cout << *i << ' ';
//     cout << newl;
// } 
//Constants
const int MOD =  1e9+7; // 998244353
// const int SMALLMOD = 998244353;
const int INF = 2e9+1337;
const ll EXCEED = 2e18+1337;
const ll GRAVITY = 8e18;

//#define vectorIO(n, MikuBondage) fun (j, n) {int i; cin >> i; MikuBondage.pb(i);}
void vectorIO(int n, vector<int> &DontUseThisName) {
    fun (j, n) {int i; cin >> i; DontUseThisName.pb(i);}
}
//#define vector2IO(n, MikuBondage) fun (j, n) {int i, ii; cin >> i >> ii; MikuBondage.pb(mp(i, ii));}
void vector2IO(int n, vector<p2> &DontUseThisName) {
    fun (j, n) {int i, ii; cin >> i >> ii; DontUseThisName.pb(mp(i, ii));}
}

const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
#define shortest_path_queue priority_queue<p2, vector<p2>, greater<p2>>
#define printArray(DontUseThisName, NakedLolisGalore, GenshinImpactClimbing) ahegao (j, NakedLolisGalore, GenshinImpactClimbing + 1) cout << DontUseThisName[j] << ' '; cout << newl;
#define print2dArray(SplitComplexProblemsIntoMultipleParts, ScuteSwarm, GenshinImpactClimbing) fun (i, ScuteSwarm) {fun (j, GenshinImpactClimbing) cout << SplitComplexProblemsIntoMultipleParts[i][j] << ' '; cout << newl;}
//}
// #define debugModifiedGraph
// #define debugLCA
// #define debugBIT
const int MAX = 200005;
vector<int> cost[MAX];
vector<p2> adj[MAX], adj2[MAX];
int pos[MAX], sparse[MAX][19], lower[MAX], upper[MAX], depth[MAX], weight[MAX], val[MAX], to[MAX], from[MAX], l[MAX], r[MAX], maxGold[MAX], maxSilver[MAX], res[MAX];
bool done[MAX];
vector<p2> ord, MikuBondage, lll;
int n, m, q, curr, temp;

void dfs1(int x, int from, int k) {
    pos[x] = k;
    fur (i, adj[x]) if (i.first != from) {
        if (cost[i.second].empty()) dfs1(i.first, x, k);
        else {
            curr += 1;
            adj2[k].pb({curr, i.second});
            adj2[curr].pb({k, i.second});
            dfs1(i.first, x, curr);
        }
    }
}

void dfs2(int x, int from, int dist) {
    temp++;
    depth[x] = dist;
    sparse[temp][0] = x;
    lower[x] = temp;
    fur (i, adj2[x]) if (i.first != from) {
        dfs2(i.first, x, dist + sz(cost[i.second]));
        
        fur (j, cost[i.second]) {
            ord.pb({j, i.first});
            #ifdef debugModifiedGraph
            weight[i.first] += j;
            #endif
        }
        temp++;
        sparse[temp][0] = x;
    }
    upper[x] = temp;
}

bool check(int a, int b) {
    return depth[a] < depth[b];
}

void buildSparseTable() {
    #ifdef debugLCA
    fun (i, temp) cout << sparse[i][0] << ' ';
    #endif
    fun (k, 18) {
        #ifdef debugLCA
        cout << newl;
        #endif
        fun (i, temp - (1 << k) + 1) {
            sparse[i][k] = min(sparse[i][k-1], sparse[i + (1 << (k - 1))][k-1], check);
            #ifdef debugLCA
            cout << sparse[i][k] << ' ';
            #endif
        }
    }
}

int lca(int l, int r) {
    
    #ifdef debugLCA
    pv(l, r, lower[l], lower[r]);
    #endif
    
    l = lower[l];
    r = lower[r];
    if (l > r) swap(l, r);
    int j = 1;
    while ((1 << j) < r - l + 1) j++;
    j--;
    
    return(min(sparse[l][j], sparse[r - (1 << j) + 1][j], check));
}

inline int query(int x) {
    if (x == 0) return 0;
    x = lower[x];
    int _curr = 0, _res = 0;
    baka (i, 18, -1) if (x & (1 << i)) {
        _curr += (1 << i);
        _res += val[_curr];
        // pv(curr, i, val[curr]);
    }
    return _res;
}

inline void modify(int x, int k) {
    int i = 0;
    while (x < MAX) {
        val[x] += k;
        // pv(x, k);
        // x = x - (x % (1 << i)) + (1 << i) * ;
        while ((x & (1 << i)) == 0) i++;
        x += (1 << i);
    }
}

signed main() {
    fastIO;
    cin >> n >> m >> q;
    numberedEdgeIO(n-1);
    fun (i, m) {
        int a, b; cin >> a >> b;
        cost[a].pb(b);
    }
    curr = 1;
    dfs1(1, -1, 1);
    // {
    dfs2(1, -1, 1);
    #ifdef debugModifiedGraph
    printArray(pos, 1, n);
    printArray(weight, 1, curr);
    printArray(depth, 1, curr);
    fun (i, curr) fur (j, adj2[i]) if (i < j.first) pv(i, j.first);
    #endif
    // }
    
    buildSparseTable();
    // {
    #ifdef debugLCA
    pv(lca(4, 5));
    #endif
    // }
    // printVector(ord);
    Sort(ord);
    fun (i, q) {
        cin >> to[i] >> from[i] >> maxGold[i] >> maxSilver[i];
        to[i] = pos[to[i]];
        from[i] = pos[from[i]];
        l[i] = 0;
        r[i] = sz(ord);
    }
    bool finished = false;
    while (not finished) {
        finished = true;
        fun (i, q) {
            if (not done[i]) {
                if (l[i] < r[i]) {
                    
                    int mid = (l[i] + r[i] + 1) / 2;
                    // pv(l[i], r[i], mid);
                    MikuBondage.pb({mid, i});
                    finished = false;
                } else {
                    // pv(i, l[i]);
                    lll.pb({l[i], i});
                    done[i] = true;
                }
            }
        }
        memset(val, 0, (temp + 2) * sizeof(int));
        Sort(MikuBondage);
        int pointer = 0;
        fur (rozalinBestWaifu, MikuBondage) {
            int t = rozalinBestWaifu.first;
            int i = rozalinBestWaifu.second;
            while (pointer < t) {
                modify(lower[ord[pointer].second], ord[pointer].first);
                modify(upper[ord[pointer].second] + 1, -ord[pointer].first);
                // {
                #ifdef debugBIT
                pv(ord[pointer]);
                pv(lower[ord[pointer].second], upper[ord[pointer].second]);
                printArray(val, 1, 16);
                #endif
                // }
                pointer++;
            }
            // pv(i, t, from[i], query(from[i]), to[i], query(to[i]));
            // pv(lca(from[i], to[i]), query(lca(from[i], to[i])), maxSilver[i]);
            if (query(from[i]) + query(to[i]) - 2 * query(lca(from[i], to[i])) <= maxSilver[i]) {
                l[i] = t;
            } else {
                r[i] = t - 1;
            }
        }
        // break;
        MikuBondage.clear();
    }
    memset(val, 0, (temp + 2) * sizeof(int));
    Sort(lll);
    int pointer = 0;
    fur (rozalinBestWaifu, lll) {
        int t = rozalinBestWaifu.first;
        int i = rozalinBestWaifu.second;
        while (pointer < t) {
            modify(lower[ord[pointer].second], 1);
            modify(upper[ord[pointer].second] + 1, -1);
            // {
            #ifdef debugBIT
            pv(ord[pointer]);
            pv(lower[ord[pointer].second], upper[ord[pointer].second]);
            printArray(val, 1, 16);
            #endif
            // }
            pointer++;
        }
        
        res[i] = max(maxGold[i] - depth[from[i]] - depth[to[i]] + 2 * depth[lca(from[i], to[i])]
        + (query(from[i]) + query(to[i]) - 2 * query(lca(from[i], to[i]))), -1);
    }
    fun (i, q) cout << res[i] << newl;

}

Compilation message (stderr)

currencies.cpp: In function 'void printVector(std::vector<int>)':
currencies.cpp:54:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 | #define fur(i, n) for (auto i : (n))
      |                   ^~~
currencies.cpp:75:5: note: in expansion of macro 'fur'
   75 |     fur (i, DontUseThisName) cout << i << ' '; cout << newl;
      |     ^~~
currencies.cpp:75:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |     fur (i, DontUseThisName) cout << i << ' '; cout << newl;
      |                                                ^~~~
currencies.cpp: In function 'void printVector(std::vector<std::pair<int, int> >)':
currencies.cpp:54:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 | #define fur(i, n) for (auto i : (n))
      |                   ^~~
currencies.cpp:78:5: note: in expansion of macro 'fur'
   78 |     fur (i, DontUseThisName) cout << i.first << ' ' << i.second << newl; cout << newl;
      |     ^~~
currencies.cpp:78:74: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |     fur (i, DontUseThisName) cout << i.first << ' ' << i.second << newl; cout << newl;
      |                                                                          ^~~~
currencies.cpp: In function 'void printVector(std::vector<std::vector<int> >)':
currencies.cpp:54:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 | #define fur(i, n) for (auto i : (n))
      |                   ^~~
currencies.cpp:81:5: note: in expansion of macro 'fur'
   81 |     fur (i, DontUseThisName) printVector(i); cout << newl;
      |     ^~~
currencies.cpp:81:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |     fur (i, DontUseThisName) printVector(i); cout << newl;
      |                                              ^~~~

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