Submission #987899

#TimeUsernameProblemLanguageResultExecution timeMemory
987899activedeltorreShopping Plans (CCO20_day2problem3)C++17
Compilation error
0 ms0 KiB
///OWNERUL LUI CALIN <3 #include <iostream> #include <vector> #include <queue> #include <algorithm> #pragma GCC optimize("O1") #pragma GCC optimize("O2") #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; long long inf=1e9+10; struct node { long long layer,sum,bitipref,lst,rghtbord,biti; }; 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]; long long init[200005]; node special(node curr) { long long g,g2; g=ord[curr.layer]; g2=ord[curr.layer+1]; curr.lst=0; curr.sum+=adj[g2][0]; curr.layer++; curr.biti=1; curr.bitipref=0; curr.rghtbord=adj[g2].size()-1; return curr; } node skip(node curr) { long long g,g2; g=ord[curr.layer]; g2=ord[curr.layer+1]; if(x[g]==0) { curr.sum=curr.sum-adj[g][curr.lst]; } else curr.sum=curr.sum-adj[g][curr.lst]+adj[g][curr.lst-1]; if(x[g2]==0) { return special(curr); } curr.layer++; curr.biti=x[g2]; curr.lst=x[g2]; curr.bitipref=x[g2]-1; curr.rghtbord=adj[g2].size()-1; curr.sum+=adj[g2][curr.lst]-adj[g2][curr.lst-1]; return curr; } node godown(node curr) { lint g,g2; g=ord[curr.layer]; g2=ord[curr.layer+1]; if(x[g2]==0) { return special(curr); } curr.layer++; curr.biti=x[g2]; curr.lst=x[g2]; curr.bitipref=x[g2]-1; curr.rghtbord=adj[g2].size()-1; 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+=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.bitipref--; 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+=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 { 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; } if(x[i]==0) { if(adj[i].size()==0) { cost[i]=inf; } else { init[i]=adj[i][0]; cost[i]=adj[i][0]; } } else { long long vkuk=adj[i][0]; init[i]=adj[i][0]; for(long long 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]]-adj[i][x[i]-1]; } } } 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]; if(x[g]==0) { curr.layer=0; curr.sum=adj[g][0]; curr.bitipref=0; curr.lst=0; curr.biti=1; curr.rghtbord=adj[g].size()-1; pq.push(curr); } else { 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(x[g]==0 && curr.biti==1 && curr.layer+1<=m && curr.lst==0) { curr2=skip(curr); pq.push(curr2); } 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); } } } while(k) { k--; cout<<-1<<'\n'; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'node special(node)':
Main.cpp:39:15: warning: variable 'g' set but not used [-Wunused-but-set-variable]
   39 |     long long g,g2;
      |               ^
Main.cpp: In function 'node godown(node)':
Main.cpp:75:5: error: 'lint' was not declared in this scope; did you mean 'uint'?
   75 |     lint g,g2;
      |     ^~~~
      |     uint
Main.cpp:76:5: error: 'g' was not declared in this scope
   76 |     g=ord[curr.layer];
      |     ^
Main.cpp:77:5: error: 'g2' was not declared in this scope
   77 |     g2=ord[curr.layer+1];
      |     ^~
Main.cpp: In function 'int main()':
Main.cpp:141:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  141 |             if(adj[i].size()<x[i])
      |                ~~~~~~~~~~~~~^~~~~
Main.cpp:165:37: 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]
  165 |                 for(long long j=0; j<adj[i].size(); j++)
      |                                    ~^~~~~~~~~~~~~~
Main.cpp:173:33: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  173 |                 if(adj[i].size()==x[i])
      |                    ~~~~~~~~~~~~~^~~~~~
Main.cpp:187: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]
  187 |     for(i=0; i<ord.size(); i++)
      |              ~^~~~~~~~~~~
Main.cpp:130:21: warning: unused variable 'minim' [-Wunused-variable]
  130 |     long long imp=0,minim=inf,poz=m;
      |                     ^~~~~
Main.cpp:130:31: warning: unused variable 'poz' [-Wunused-variable]
  130 |     long long imp=0,minim=inf,poz=m;
      |                               ^~~