Submission #892901

#TimeUsernameProblemLanguageResultExecution timeMemory
892901Faisal_SaqibSky Walking (IOI19_walk)C++17
10 / 100
4051 ms259292 KiB
#include <vector> #include <map> #include <set> #include <iostream> #include <algorithm> using namespace std; map<pair<int,int>,vector<pair<int,int>>> ma; map<int,vector<int>> at; map<pair<int,int>,bool> vis; map<int,vector<int>> add_at; map<int,vector<int>> rem_at; map<int,int> prev1; long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { set<int> sp(begin(h),end(h)); int n=x.size(); int m=l.size(); if(sp.size()==1) { for(int i=0;i<n;i++) { at[i].push_back(0); at[i].push_back(h[i]); } for(int i=0;i<m;i++) { add_at[l[i]].push_back(y[i]); rem_at[r[i]+1].push_back(y[i]); prev1[y[i]]=-1; } set<int> cur; for(int i=0;i<n;i++) { for(auto j:rem_at[i]) { cur.erase(j); } for(auto j:add_at[i]) { cur.insert(j); } auto it=begin(cur); while(it!=end(cur) and (*it)<=h[i]) { at[i].push_back(*it); if(prev1[*it]==-1) { prev1[*it]=i; } else { ma[{x[prev1[*it]],*it}].push_back({x[i],*it}); ma[{x[i],*it}].push_back({x[prev1[*it]],*it}); } it++; } } for(int i=0;i<n;i++) { sort(begin(at[i]),end(at[i])); for(int j=1;j<at[i].size();j++) { ma[{x[i],at[i][j]}].push_back({x[i],at[i][j-1]}); ma[{x[i],at[i][j-1]}].push_back({x[i],at[i][j]}); } } set<vector<long long>> di; di.insert({0,x[s],0}); while(di.size()) { auto fi=*begin(di); di.erase(begin(di)); if(vis[{fi[1],fi[2]}]) continue; // cout<<"I am "<<fi[0]<<' '<<fi[1]<<' '<<fi[2]<<endl; if(fi[1]==x[g] and fi[2]==0) { return fi[0]; } vis[{fi[1],fi[2]}]=1; for(auto [nx,ny]:ma[{fi[1],fi[2]}]) { // cout<<"From "<<fi[1]<<' '<<fi[2]<<" can go to "<<nx<<' '<<ny<<endl; di.insert({fi[0]+abs(nx-fi[1])+abs(fi[2]-ny),nx,ny}); } } return -1; } // if(n<=50 and m<=50) { for(int i=0;i<n;i++) { at[i].push_back(0); at[i].push_back(h[i]); } for(int j=0;j<m;j++) { int sb=l[j]; int eb=r[j]; int prev=-1; for(;sb<=eb;sb++) { if(h[sb]>=y[j]) { at[sb].push_back(y[j]); if(prev!=-1) { ma[{x[prev],y[j]}].push_back({x[sb],y[j]}); ma[{x[sb],y[j]}].push_back({x[prev],y[j]}); } prev=sb; } } } for(int i=0;i<n;i++) { sort(begin(at[i]),end(at[i])); for(int j=1;j<at[i].size();j++) { ma[{x[i],at[i][j]}].push_back({x[i],at[i][j-1]}); ma[{x[i],at[i][j-1]}].push_back({x[i],at[i][j]}); } } set<vector<long long>> di; di.insert({0,x[s],0}); while(di.size()) { auto fi=*begin(di); di.erase(begin(di)); if(vis[{fi[1],fi[2]}]) continue; // cout<<"I am "<<fi[0]<<' '<<fi[1]<<' '<<fi[2]<<endl; if(fi[1]==x[g] and fi[2]==0) { return fi[0]; } vis[{fi[1],fi[2]}]=1; for(auto [nx,ny]:ma[{fi[1],fi[2]}]) { // cout<<"From "<<fi[1]<<' '<<fi[2]<<" can go to "<<nx<<' '<<ny<<endl; di.insert({fi[0]+abs(nx-fi[1])+abs(fi[2]-ny),nx,ny}); } } } return -1; }

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for(int j=1;j<at[i].size();j++)
      |                ~^~~~~~~~~~~~~
walk.cpp:118:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |    for(int j=1;j<at[i].size();j++)
      |                ~^~~~~~~~~~~~~
#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...