제출 #782302

#제출 시각아이디문제언어결과실행 시간메모리
782302AmirElarbiTwo Currencies (JOI23_currencies)C++14
0 / 100
6 ms5348 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define INF 1e9 #define ve vector #define vi ve<int> #define ii pair<int,int> #define vii ve<ii> #define pb push_back #define fi first #define se second #define ll long long using namespace __gnu_pbds; using namespace std; const int nax = 1e5+5; const int kax = 25+5; const int MOD = 1e9+7; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int cnt = 0, cur = 0, tin[nax], tout[nax], up[nax][kax]; vii adj[nax]; ll dep[nax], w[nax]; int dfs(int u, int p){ tin[u] = cur++; up[u][0] = p; for(int i = 1; i < kax; i++) up[u][i] = up[up[u][i-1]][i-1]; for(auto x : adj[u]){ if(x.fi == p) continue; dep[x.fi] = dep[u]+w[x.se]; dfs(x.fi,u); } tout[u] = cur++; } bool is_anc(int u, int v){ return (tin[u] <= tin[v] && tout[v] <= tout[u]); } int lca(int u, int v){ if(is_anc(u,v)) return u; if(is_anc(v,u)) return v; for(int i = kax-1; i >= 0; i--) if(!is_anc(up[u][i], v)) u = up[u][i]; return up[u][0]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m,q; cin >> n >> m >> q; for (int i = 0; i < n-1; ++i) { int a,b; cin >> a >> b; a--,b--; adj[a].pb({b,i}); adj[b].pb({a,i}); } for (int i = 0; i < m; ++i) { int p; ll c; cin >> p >> c; p--; cnt = c; w[p] += c; } dfs(0,0); //cout << up[6][0] << endl; while(q--){ int s,t,x; ll y; cin >> s >> t >> x >> y; s--,t--; int l = lca(s,t); ll sm = dep[s]+dep[t]-2*dep[l]; ll gld = sm/cnt - y/cnt; //cout << l << endl; if(gld <= 0) cout << x << endl; else if(gld <= x) cout << x-gld << endl; else cout << -1 << endl; } }

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

currencies.cpp: In function 'int dfs(int, int)':
currencies.cpp:32:1: warning: no return statement in function returning non-void [-Wreturn-type]
   32 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...