oj.uz

Submission #893006

# Submission time Handle Problem Language Result Execution time Memory
893006 2023-12-26T10:07:15 Z Faisal_Saqib Sky Walking (IOI19_walk) C++17
0 / 100
 3054 ms 288348 KB 
#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])
			{
				prev1[j]=-1;
				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)
				{
					// cout<<"There is a edge "<<x[prev1[*it]]<<' '<<*it<<' '<<x[i]<<' '<<*it<<endl;
					ma[{x[prev1[*it]],*it}].push_back({x[i],*it});
					ma[{x[i],*it}].push_back({x[prev1[*it]],*it});	
				}
				prev1[*it]=i;
				it++;
			}
		}
		for(int i=0;i<n;i++)
		{
			sort(begin(at[i]),end(at[i]));
			// cout<<"For "<<i<<endl;;
			// for(auto j:at[i])
			// {
			// 	cout<<j<<' ';
			// }
			// cout<<endl;
			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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 888 ms 126204 KB Output is correct
4 Correct 2247 ms 230576 KB Output is correct
5 Correct 1053 ms 156652 KB Output is correct
6 Correct 980 ms 143512 KB Output is correct
7 Correct 1049 ms 157308 KB Output is correct
8 Correct 1422 ms 166092 KB Output is correct
9 Correct 1223 ms 157120 KB Output is correct
10 Correct 3054 ms 288348 KB Output is correct
11 Correct 802 ms 93836 KB Output is correct
12 Correct 982 ms 122276 KB Output is correct
13 Correct 2748 ms 271832 KB Output is correct
14 Correct 633 ms 88580 KB Output is correct
15 Incorrect 633 ms 88976 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 12668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 12668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -