제출 #745005

#제출 시각아이디문제언어결과실행 시간메모리
745005onebit1024Two Currencies (JOI23_currencies)C++17
10 / 100
5084 ms42208 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define all(c) c.begin(), c.end() #define endl "\n" const double PI=3.141592653589; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x) #else #define dbg(x...) #endif int n,m,q; vector<vector<int>>adj, up,tax; vector<int>par,dist; void comp(int u, int p){ for(int v : adj[u]){ if(v==p)continue; par[v] = u; dist[v] = dist[u]+1; up[v][0] = u; for(int j = 1;j<=20;++j)up[v][j] = up[up[v][j-1]][j-1]; comp(v,u); } } int lca(int u, int v){ if(dist[v] > dist[u])swap(v,u); int k = dist[u]-dist[v]; for(int j = 0;j<=20;++j){ if(k&(1ll<<j))u = up[u][j]; } if(u==v)return u; for(int j = 20;j>=0;--j){ if(up[u][j] != up[v][j])u = up[u][j], v = up[v][j]; } return up[v][0]; } void solve() { cin >> n >> m >> q; adj.resize(n+1); up = vector<vector<int>>(n+1, vector<int>(21)); vector<pair<int,int>>edges = {{0,0}}; dist.resize(n+1); tax.resize(n+1); par.resize(n+1); for(int i = 1;i<n;++i){ int u,v; cin >> u >> v; edges.pb({u,v}); adj[u].pb(v); adj[v].pb(u); } comp(1,-1); for(int i = 1;i<=m;++i){ int p,c; cin >> p >> c; int u = edges[p].first, v = edges[p].second; if(par[u] == v)swap(v,u); // par[v] = u tax[v].pb(c); } while(q--){ int u,v,g,s; cin >> u >> v >> g >> s; int l = lca(u,v); vector<int>res; while(u!=l){ for(auto x : tax[u])res.pb(x); u = par[u]; } while(v!=l){ for(auto x : tax[v])res.pb(x); v = par[v]; } sort(all(res)); bool got = 0; for(int i = 0;i<res.size();++i){ if(s>=res[i])s-=res[i]; else{ int need = res.size()-i; int val = g-need; if(val < 0)val = -1; cout << val << endl; got = 1; break; } } if(!got)cout << g << endl; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int T=1; for(int i = 1;i<=T;++i) { // cout << "Case #" << i << ": "; solve(); } }

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

currencies.cpp: In function 'void solve()':
currencies.cpp:106:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i = 0;i<res.size();++i){
      |                       ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...