Submission #946486

#TimeUsernameProblemLanguageResultExecution timeMemory
946486PM1Watermelon (INOI20_watermelon)C++17
0 / 100
42 ms17624 KiB
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second const int mxn=1e5+5; int n,k,a[mxn],par[mxn],ans=0,res[mxn],mx,dis[mxn],sz[mxn]; vector<int>v[mxn],state[mxn]; set<int>s; set<pair<int,int>>tree; void dfs(int z){ bool cnt=0; for(auto i:v[z]){ if(par[z]!=i){ cnt=1; dfs(i); sz[z]++; } } if(!cnt)s.insert(z); } void solve(int x=1){ if(x==n+1){ ans++; return; } assert(s.size()); auto y=s.upper_bound(0); while(y!=s.end()){ int z=*y; s.erase(z); sz[par[z]]--; if(!sz[par[z]]) s.insert(par[z]); solve(x+1); s.insert(z); sz[par[z]]++; if(sz[par[z]]) s.erase(par[z]); y=s.upper_bound(z); if(ans==k){ res[z]=x; break; } } } void make(int x,int y){ //cout<<x<<" "<<y<<'\n'; par[y]=x; dis[y]=dis[x]+1; tree.insert({x,dis[x]}); tree.insert({y,dis[y]}); v[x].push_back(y); v[y].push_back(x); } int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; if(a[i]==-1){ state[n+1].push_back(i); } else{ state[a[i]].push_back(i); mx=max(mx,a[i]); } } for(int i=1;i<state[n+1].size();i++){ make(state[n+1][i-1],state[n+1][i]); } while(mx){ if(state[mx].size()==0){ cout<<-1; return 0; } reverse(state[mx].begin(),state[mx].end()); for(auto i:state[mx]){ auto x=tree.lower_bound(make_pair(i,0)); if(x==tree.end()){ x--; make(x->fr,i); continue; } if(x==tree.begin()){ make(x->fr,i); continue; } auto y=x; y--; if(x->sc<y->sc) make(y->fr,i); else make(x->fr,i); } mx--; } dfs(state[n+1][0]); solve(); if(ans<k){ cout<<-1; } else{ for(int i=1;i<=n;i++){ cout<<res[i]<<" "; } } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=1;i<state[n+1].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...
#Verdict Execution timeMemoryGrader output
Fetching results...