Submission #987870

#TimeUsernameProblemLanguageResultExecution timeMemory
987870activedeltorreShopping Plans (CCO20_day2problem3)C++14
15 / 25
207 ms45224 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; //ifstream cin("a.in"); //ofstream cout("a.out"); long long inf=1e9+10; struct node { long long layer,sum,bitipref,lst,rghtbord,biti; // node(int a,int b,int c,int d,int e) : layer(a),sum(b),bitipref(c),lst(d),rghtbord(e){} }; struct cmp { bool operator()(node a,node b) { return a.sum>b.sum; } }; priority_queue<node,vector<node>,cmp>pq; vector<long long >arr; vector<long long >adj[200005]; long long cost[200005]; vector<long long>ord; bool cmp2(long long a,long long b) { return cost[a]<cost[b]; } int y[200005]; int x[200005]; int init[200005]; node skip(node curr) { int g,g2; g=ord[curr.layer]; g2=ord[curr.layer+1]; curr.sum=curr.sum-adj[g][curr.lst]+adj[g][curr.lst-1]; curr.layer++; curr.biti=x[g2]; curr.lst=x[g2]; curr.bitipref=x[g2]-1; curr.rghtbord=adj[g2].size()-1; curr.sum=curr.sum+adj[g2][curr.lst]-adj[g2][curr.lst-1]; return curr; } node godown(node curr) { int g,g2; g=ord[curr.layer]; g2=ord[curr.layer+1]; curr.layer++; curr.biti=x[g2]; curr.lst=x[g2]; curr.bitipref=x[g2]-1; curr.rghtbord=adj[g2].size()-1; curr.sum=curr.sum+adj[g2][curr.lst]-adj[g2][curr.lst-1]; return curr; } node shift(node curr) { int g; g=ord[curr.layer]; curr.lst++; curr.sum=curr.sum+adj[g][curr.lst]-adj[g][curr.lst-1]; return curr; } node fixborderandshift(node curr) { int g; g=ord[curr.layer]; curr.rghtbord=curr.lst-1; curr.lst=curr.bitipref; curr.sum=curr.sum+adj[g][curr.lst]-adj[g][curr.lst-1]; return curr; } node fixborderandcreate(node curr) { int g; g=ord[curr.layer]; curr.rghtbord=curr.lst-1; curr.lst=0; curr.biti++; curr.sum=curr.sum+init[g]; return curr; } signed main() { long long n,m,k,i,a,b; long long sum=0; ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m>>k; for(i=1; i<=n; i++) { cin>>a>>b; adj[a].push_back(b); } long long imp=0,minim=inf,poz=m; for(i=1; i<=m; i++) { cin>>x[i]>>y[i]; if(y[i]==0) { cost[i]=inf; } else { if(x[i]==0) { adj[i].push_back(0); x[i]=1; } sort(adj[i].begin(),adj[i].end()); if(adj[i].size()<x[i]) { for(long long j=1; j<=k; j++) { cout<<-1<<'\n'; } return 0; } int vkuk=adj[i][0]; init[i]=adj[i][0]; for(int j=0; j<adj[i].size(); j++) { if(j+1<=x[i]) { sum+=adj[i][j]; } adj[i][j]-=vkuk; } if(adj[i].size()==x[i]) { cost[i]=inf; } else { cost[i]=adj[i][x[i]]; } } ord.push_back(i); } sort(ord.begin(),ord.end(),cmp2); m--; for(i=0; i<ord.size(); i++) { if(cost[ord[i]]==inf) { m=i-1; break; } } node curr,curr2; cout<<sum<<'\n'; k--; if(m>=0) { int g=ord[0]; curr.layer=0; curr.sum=adj[g][x[g]]-adj[g][x[g]-1]; curr.bitipref=x[g]-1; curr.lst=x[g]; curr.rghtbord=adj[g].size()-1; curr.biti=x[g]; pq.push(curr); while(pq.size() && k && imp==0) { curr=pq.top(); pq.pop(); k--; cout<<curr.sum+sum<<'\n'; g=ord[curr.layer]; if(curr.lst==x[g] && curr.bitipref==x[g]-1 && curr.biti==x[g] && curr.layer+1<=m) { curr2=skip(curr); pq.push(curr2); } if(curr.lst+1<=curr.rghtbord) { curr2=shift(curr); pq.push(curr2); } if(curr.bitipref>=1 && curr.lst>=curr.bitipref+1) { curr2=fixborderandshift(curr); pq.push(curr2); } if(curr.bitipref==0 && curr.lst>=1 && curr.biti+1<=y[g]) { curr2=fixborderandcreate(curr); pq.push(curr2); } if(curr.layer+1<=m) { curr2=godown(curr); pq.push(curr2); } /* if(curr.lst==1 && curr.layer+1<=m) { curr2=curr; curr2.layer++; curr2.biti=1; curr2.sum=curr2.sum-adj[ord[curr.layer]][1]+adj[ord[curr.layer+1]][1]; pq.push(curr2); } if(curr.layer+1<=m) { curr2=curr; curr2.layer++; curr2.lst=1; curr2.biti=1; curr2.sum=curr2.sum+adj[ord[curr.layer+1]][1]; pq.push(curr2); } if(adj[ord[curr.layer]].size()>curr.lst+1 && curr.biti+1<=y[ord[curr.layer]]) { curr2=curr; curr2.lst++; curr2.biti++; curr2.sum+=adj[ord[curr.layer]][curr2.lst]; pq.push(curr2); } if(adj[ord[curr.layer]].size()>curr.lst+1) { curr2=curr; curr2.sum=curr.sum-adj[ord[curr.layer]][curr.lst]+adj[ord[curr.layer]][curr.lst+1]; curr2.lst++; pq.push(curr2); }*/ } } while(k) { k--; cout<<-1<<'\n'; } return 0; } /* 5 2 7 1 5 1 3 2 3 1 6 2 1 1 1 1 1*/

Compilation message (stderr)

Main.cpp: In function 'node godown(node)':
Main.cpp:50:9: warning: variable 'g' set but not used [-Wunused-but-set-variable]
   50 |     int g,g2;
      |         ^
Main.cpp: In function 'int main()':
Main.cpp:116:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |             if(adj[i].size()<x[i])
      |                ~~~~~~~~~~~~~^~~~~
Main.cpp:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             for(int j=0; j<adj[i].size(); j++)
      |                          ~^~~~~~~~~~~~~~
Main.cpp:134:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |             if(adj[i].size()==x[i])
      |                ~~~~~~~~~~~~~^~~~~~
Main.cpp:147:15: 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]
  147 |     for(i=0; i<ord.size(); i++)
      |              ~^~~~~~~~~~~
Main.cpp:100:21: warning: unused variable 'minim' [-Wunused-variable]
  100 |     long long imp=0,minim=inf,poz=m;
      |                     ^~~~~
Main.cpp:100:31: warning: unused variable 'poz' [-Wunused-variable]
  100 |     long long imp=0,minim=inf,poz=m;
      |                               ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...