Submission #888706

#TimeUsernameProblemLanguageResultExecution timeMemory
888706vjudge1Two Currencies (JOI23_currencies)C++17
10 / 100
213 ms74452 KiB
#include <bits/stdc++.h> #define ll long long #define str string #define ins insert #define ld long double #define pb push_back #define pf push_front #define pof pop_front() #define pob pop_back() #define lb lower_bound #define ub upper_bound #define endl "\n" #define fr first #define sc second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define sz size() #define bc back() #define ar array #define vll vector<ll> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <class _T> bool chmin(_T &x, const _T &y){ bool flag=false; if(x>y){ x=y;flag|=true; } return flag; } template <class _T> bool chmax(_T &x, const _T &y){ bool flag=false; if (x<y){ x=y;flag|=true; } return flag; } #define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} void start(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const ll inf=2e18+7; const ll mod=1e9+7; const ll N=1e5+7; const ld eps=1e-9; vector<vector<pair<ll,vll>>> g(N); ll p[N][20],d[N],num[N][20]; vector<vll> pv(N); void dfs(ll v){ for(ll i=1;i<5;i++){ p[v][i]=p[p[v][i-1]][i-1]; num[v][i]=num[v][i-1]+num[p[v][i-1]][i-1]; } for(auto i : g[v]){ if(i.fr==p[v][0])continue; ll to=i.fr; for(auto j : i.sc){ pv[to].pb(j); } p[to][0]=v; num[to][0]=pv[to].sz; d[to]=d[v]+1; dfs(to); } } ll lca(ll a,ll b){ if(d[a]<d[b])swap(a,b); ll sum=0; ll i; for(i=18;i>=0;i--){ if(d[a]-d[b]>=(1ll<<i)){ sum+=num[a][i]; a=p[a][i]; } } if(a==b) return sum; for(i=18;i>=0;i--){ if(p[a][i]!=p[b][i]){ sum+=num[a][i]+num[b][i]; a=p[a][i]; b=p[b][i]; } } return sum+num[a][0]+num[b][0]; } void solve(){ ll i,j,q; ll n,m,a,b; cin>>n>>m>>q; bool flag=true; vector<pair<pair<ll,ll>,vll>> v(n-1); for(i=0;i<n-1;i++){ cin>>v[i].fr.fr>>v[i].fr.sc; } ll lst=-1; for(j=0;j<m;j++){ cin>>a; cin>>b; if(lst && lst!=b)flag=false; v[--a].sc.pb(b); lst=b; } for(i=0;i<n-1;i++){ a=v[i].fr.fr,b=v[i].fr.sc; g[a].pb({b,v[i].sc}); g[b].pb({a,v[i].sc}); } dfs(1); ll x,y; if(n<=2000 && m<=2000 && q<=2000){ for(i=0;i<q;i++){ cin>>a>>b; cin>>x>>y; if(d[a]<d[b])swap(a,b); vector<ll> v; while(d[a]>d[b]){ for(auto j : pv[a])v.pb(j); a=p[a][0]; } while(a!=b){ for(auto j : pv[a])v.pb(j); a=p[a][0]; for(auto j : pv[b])v.pb(j); b=p[b][0]; } sort(all(v)); for(auto j : v){ if(y>=j)y-=j; else x--; } if(x<0)cout<<-1<<endl; else cout<<x<<endl; } return; } for(i=0;i<q;i++){ cin>>a>>b; cin>>x>>y; ll w=lca(a,b); for(j=0;j<w;j++){ if(y>=lst)y-=lst; else x--; } if(x<0)cout<<-1<<endl; else cout<<x<<endl; } return; } signed main(){ start(); ll t=1; //cin>>t; while(t--) solve(); return 0; } /* 1 6 5 4 3 2 1 0 */

Compilation message (stderr)

currencies.cpp: In function 'void solve()':
currencies.cpp:96:7: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   96 |  bool flag=true;
      |       ^~~~
currencies.cpp: In function 'void fre(std::string)':
currencies.cpp:42:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:42:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".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...