제출 #396827

#제출 시각아이디문제언어결과실행 시간메모리
396827Pichon5Fountain (eJOI20_fountain)C++17
30 / 100
80 ms10648 KiB
#include <iostream> #include <bits/stdc++.h> #define vi vector<int> #define pb push_back #define F first #define S second #define ll long long #define vll vector<ll> using namespace std; const int tam=1e5+5; int T[tam]; vi v; void init(int nodo,int b, int e){ int L=2*nodo+1,R=L+1,mid=(b+e)/2; if(b==e){ T[nodo]=v[b]; return; } init(L,b,mid);init(R,mid+1,e); T[nodo]=max(T[L],T[R]); } int query(int nodo, int b, int e, int izq, int der){ int L=2*nodo+1,R=L+1,mid=(b+e)/2; if(b>=izq && e<=der){ return T[nodo]; } if(der<=mid){ return query(L,b,mid,izq,der); } if(izq>=mid+1){ return query(R,mid+1,e,izq,der); } return max(query(L,b,mid,izq,der),query(R,mid+1,e,izq,der)); } vi G[tam+5]; vll C; int dp[tam][20]; int depth[tam]; ll peso[tam]; void init(int nodo,int p ,int d,int P){ peso[nodo]=P; depth[nodo]=d; dp[nodo][0]=p; for(int i=0;i<G[nodo].size();i++){ int it=G[nodo][i]; if(it==p)continue; //cout<<C.size()<<endl; //cout<<"hijo "<<it<<" "<<P+C[it-1]<<endl; init(it,nodo,d+1,P+C[it-1]); } } void initbl(){ init(0,-1,0,1e9); for(int i=1;i<=19;i++){ for(int l=0;l<tam;l++){ if(dp[l][i-1]==-1)continue; dp[l][i]=dp[dp[l][i-1]][i-1]; } } } pair<int,int> _find(int nodo, int num){//retorna la suma y el indice int nodoin=nodo; for(int i=19;i>=0;i--){ if(num&(1<<i)){ nodo=dp[nodo][i]; } } //cout<<peso[nodoin]<<" "<<peso[nodo]<<endl; //cout<<peso[nodoin]-peso[nodo-1]<<endl; return {peso[nodoin]-peso[nodo]+C[nodo-1],nodo}; } int main() { int n,q,d,c; cin>>n>>q; for(int i=0;i<n;i++){ cin>>d>>c; v.pb(d);C.pb(c); } v.pb(5000); init(0,0,n); for(int i=0;i<n;i++){ int b=i+1,e=n; int pos; while(b<=e){ int mid=(b+e)/2; int Q=query(0,0,n,b,mid); if(b==e){ pos=b; break; } if(Q>v[i]){ pos=mid; e=mid; }else{ b=mid+1; pos=e; } } if(pos==n){ G[i+1].pb(0);G[0].pb(i+1); }else{ G[i+1].pb(pos+1);G[pos+1].pb(i+1); } } initbl(); pair<int,int>A=_find(3,2); //cout<<"fisrt "<<A.F<<endl; //cout<<"second "<<A.S<<endl; int R,V; //return 0; while(q--){ cin>>R>>V; int b=0,e=depth[R]; int res=0,aux=20; while(b<=e && aux--){ int mid=(b+e)/2; pair<int,int> Q=_find(R,mid); if(Q.F>=V){ res=Q.S; e=mid; }else{ b=mid+1; } } if(res>n)res=0; cout<<res<<endl; } return 0; }

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

fountain.cpp: In function 'void init(int, int, int, int)':
fountain.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<G[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:108:18: warning: variable 'A' set but not used [-Wunused-but-set-variable]
  108 |     pair<int,int>A=_find(3,2);
      |                  ^
fountain.cpp:104:26: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |             G[i+1].pb(pos+1);G[pos+1].pb(i+1);
      |                       ~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...