Submission #955329

#	Time	Username	Problem	Language	Result	Execution time	Memory
955329		Requiem	Two Currencies (JOI23_currencies)	C++17	10 / 100	5028 ms	32712 KiB

currencies

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "k"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 1e5 + 9;


struct Station{
    int pos_edge;
    int fee_silver;
    Station(int pos_edge = 0, int fee_silver = 0):
        pos_edge(pos_edge), fee_silver(fee_silver){}
};
struct Query{
    int start, destination, silver, gold;
    Query(int start = 0, int destination = 0, int silver = 0, int gold = 0):
        start(start), destination(destination), silver(silver), gold(gold){}
};

int n, m, q;
vector<int> g[MAXN];     ii edge[MAXN];
vector<pair<int, Query>> SetQuery;
vector<Station> SetStation;
map<int, vector<int>> mp;

namespace sub1{
    int par[MAXN], depth[MAXN];
    void dfs(int u,int p){

        for(auto e: g[u]){
            int v = edge[e].fi + edge[e].se - u;
            if (v == p) continue;
            par[v] = e;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    int getpath(int u,int v,int gold,int silver){
         vector<int> path;
         int sum = 0;
         while(u != v){
//                cerr << u << ' ' << v << endl;
                if (depth[u] < depth[v]) swap(u, v);
                int edge_to_p = par[u];
                if (mp[edge_to_p].size() != 0){
                    for(auto v: mp[edge_to_p]){
                        path.pb(v);
                        sum += v;
                    }
                }
                u = edge[edge_to_p].fi + edge[edge_to_p].se - u;
         }
         sum = 0;
         for(auto x: path){
             sum += x;
         }
         sort(path.begin(), path.end());
         int cnt = 0;
         while(sum > silver and path.size() > 0){
               cnt++;
               sum -= path.back();
               path.pop_back();
         }
         return max(gold - cnt, -1LL);
    }
    void solve(){
        dfs(1, -1);
//        for(int i = 1; i <= n; i++){
//            cout << depth[i] << ' ' << par[i] << endl;
//        }
        for(int i = 0; i < q; i++){
            int u = SetQuery[i].se.start;
            int v = SetQuery[i].se.destination;
            int golden = SetQuery[i].se.gold;
            int silver = SetQuery[i].se.silver;
            cout << getpath(u, v, golden, silver) << endl;

        }

    }
}
main()
{
    fast;
   if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
   }
   cin >> n >> m >> q;
   for(int i = 1; i < n; i++){
       int u, v;
       cin >> u >> v;
       edge[i] = {u, v};
       g[u].pb(i);
       g[v].pb(i);
   }

   for(int i = 0; i < m; i++){
       int node, fee = 0;
       cin >> node >> fee;
       SetStation.pb(Station(node, fee));
       mp[node].pb(fee);

   }

   for(int i = 0 ; i < q; i++){
       int u, v, silver, gold;
       cin >> u >> v >> gold >> silver;
       SetQuery.pb({i, Query(u, v, silver, gold)});
   }
   sub1::solve();
}

Compilation message (stderr)

currencies.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main()
      | ^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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