Submission #888701

#TimeUsernameProblemLanguageResultExecution timeMemory
888701vjudge1Two Currencies (JOI23_currencies)C++17
28 / 100
189 ms39716 KiB
/* author : abushbandit contest : --- */ #include "bits/stdc++.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define ff first #define ss second #define pb push_back #define rep(i,s,f) for(int i = s;i < f;i++) #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #pragma GCC optimize("Ofast,no-stack-protector,fast-math",3) template <class type1> using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<pair<int,int>> vii; typedef pair<int,int> pii; const ll INF = 1e18; const ll MOD7 = 1e9 + 7; const ll MOD9 = 998244353; const ld PI = acos(-1.0); const int N = 1e5 + 6; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } int binpow (int a, int n) { int res = 1; while (n) { if (n & 1) res *= a; a *= a; n >>= 1; } return res; } void start_file(string file){ freopen((file + ".in").c_str(),"r",stdin); freopen((file + ".out").c_str(),"w",stdout); } // for second subtask vector<pair<int,int>> g[N]; int up[N][30]; int dp[N],dep[N]; int path[N]; // for first subtask vector<vector<int>> wgt(N); void dfs(int u,int pr,int de){ dep[u] = de; for(auto x : g[u]){ if(x.ff != pr){ up[x.ff][0] = u; dp[x.ff] = dp[u] + path[x.ss]; dfs(x.ff,u,de + 1); } } } int lca(int a,int b){ if(dep[a] < dep[b]) swap(a,b); int dis = dep[a] - dep[b]; for(int i = 29;i >= 0;i--) if(dis & (1 << i)){ a = up[a][i]; } if(a == b) return a; for(int i = 29;i >= 0;i--) if(up[a][i] != up[b][i]){ a = up[a][i]; b = up[b][i]; } return up[a][0]; } void clear(){ for(int i = 0;i < N;i++){ g[i].clear(); path[i] = dep[i] = dp[i] = 0; for(int j = 0;j < 30;j++) up[i][j] = 0; } return; } void scndfs(int n,int p,vector<pair<int,vector<int>>> &pr){ // cout << n << endl; // pair<int,vector<int>> q; // q.ff = p; // q.ss = v; // pr[n] = q; for(auto to : g[n]){ if(to.ff != p){ pr[to.ff] = {n,wgt[to.ss]}; // cout << "ans" << endl; scndfs(to.ff,n,pr); } } } void solve(int tc){ clear(); int n,m,q; cin >> n >> m >> q; if(n <= 2000 && m <= 200 && q <= 2000){ // int a[n],b[n]; for(int i = 0;i < n - 1;i++){ int a,b; cin >> a >> b; g[a].pb({b,i}); g[b].pb({a,i}); } for(int i = 0;i < m;i++){ int p,c; cin >> p >> c; wgt[p - 1].pb(c); } for(int i = 0;i < q;i++){ int s,t,gold,sillver; cin >> s >> t >> gold >> sillver; vector<pair<int,vector<int>>> pr(n + 1); // vector<int> v; scndfs(s,0,pr); vector<int> ans; while(t != s){ for(auto j : pr[t].ss){ ans.pb(j); } t = pr[t].ff; // cout << "asd" << endl; } sort(all(ans)); for(auto j : ans){ if(sillver >= j){ sillver -= j; } else{ gold--; } } if(gold < 0){ cout << "-1\n"; } else{ cout << gold << "\n"; } } return; } for(int i = 0;i < n - 1;i++){ int a,b; cin >> a >> b; g[a].push_back({b,i}); g[b].push_back({a,i}); } int cul; for(int i = 0;i < m;i++){ int u; cin >> u >> cul; path[u - 1]++; } dp[1] = 0; up[1][0] = 1; dfs(1,1,0); for(int j = 1;j < 30;j++) for(int i = 1;i < n + 1;i++){ up[i][j] = up[up[i][j - 1]][j - 1]; } for(int i = 0;i < q;i++){ int a,b,g,s; cin >> a >> b >> g >> s; int lc = lca(a,b); int dis = dp[a] + dp[b] - 2 * (dp[lc]); int cnt = s / cul; dis = max(0ll,dis - cnt); dis = g - dis; if(dis < 0) dis = -1; cout << dis << "\n"; } } signed main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // start_file(""); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int test_cases = 1; // cin >> test_cases ; for(int tc = 1;tc <= test_cases;++ tc){ solve(tc); } }

Compilation message (stderr)

currencies.cpp: In function 'void start_file(std::string)':
currencies.cpp:75:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  freopen((file + ".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  freopen((file + ".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...