oj.uz

Submission #133876

# Submission time Handle Problem Language Result Execution time Memory
133876 2019-07-21T16:09:03 Z arthurconmy Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 17672 KB 
#include <bits/stdc++.h>

#ifndef ARTHUR_LOCAL
	#include "wombats.h"
#endif

using namespace std;
using pii=pair<int,int>;

const int INF = 1000000000;
int r=-1;
int c=-1;
int H[5000][200];
int V[5000][200];
vector<pii> adj[10000];
int dis[10000];

void init(int r_raw, int c_raw, int H_raw[5000][200], int V_raw[5000][200])
{
	r=r_raw;
	c=c_raw;

	for(int i=0; i<5000; i++)
	{
		for(int j=0; j<200; j++)
		{
			H[i][j]=H_raw[i][j];
			V[i][j]=V_raw[i][j];
		}
	}

	for(int i=0; i<10000; i++)
	{
		int row=int(i/c);
		int col=i%c;

		if(row>=r) break;

		// << "RC: " << row << " " << col << endl;

		if(row < r-1)
		{
			// dis[i][i+c] = V[row][col];
			//cout << i << " " << i+c << " " << V[row][col] << " V" << endl;
		
			adj[i].push_back(make_pair(i+c,V[row][col]));
		}

		if(col < c-1)
		{
			// dis[i][i+1] = H[row][col];
			// dis[i+1][i] = H[row][col];
			//cout << i << " " << i+1 << " " << H[row][col] << " H" << endl;
		
			adj[i].push_back(make_pair(i+1,H[row][col]));
			adj[i+1].push_back(make_pair(i,H[row][col]));
		}
	}

	// cout << "here" << endl;
}

void changeH(int p, int q, int w)
{
	for(int i=0; i<adj[p*c + q].size(); i++)
	{
		pii u = adj[p*c + q][i];

		if(u.first == p*c + q + 1)
		{
			adj[p*c + q][i] = {u.first, w};
			break;
		}
	}

	for(int i=0; i<adj[p*c + q + 1].size(); i++)
	{
		pii u = adj[p*c + q + 1][i];

		if(u.first == p*c + q)
		{
			adj[p*c + q + 1][i] = {u.first, w};
			break;
		}
	}
}

void changeV(int p, int q, int w)
{
	for(int i=0; i<adj[p*c + q].size(); i++)
	{
		pii u = adj[p*c + q][i];

		if(u.first == p*c + q + c)
		{
			adj[p*c + q][i] = {u.first,w};
			break;
		}
	}

	for(int i=0; i<adj[p*c + q + c].size(); i++)
	{
		pii u = adj[p*c + q + c][i];

		if(u.first == p*c + q)
		{
			adj[p*c + q + c][i] = {u.first,w};
			break;
		}
	}
}


int escape(int v1, int v2)
{
	for(int i=0; i<10000; i++) dis[i]=INF;

	priority_queue<pii> PQ;
	PQ.push(make_pair(-0,v1));

	while(!PQ.empty())
	{
		int v = PQ.top().second;
		int cur_dis = -PQ.top().first;
		PQ.pop();

		if(dis[v]!=INF) continue;
		//if(v1==3) cout << v << " " << cur_dis << endl;
		dis[v]=cur_dis;

		for(auto pear:adj[v])
		{
			int jump=pear.second;
			int w=pear.first;

			if(dis[w]==INF)
			{
				PQ.push(make_pair(-cur_dis-jump,w));
			}
		}
	}

	#ifdef ARTHUR_LOCAL
		cout << dis[c*(r-1) + v2] << endl;
	#endif

	return dis[c*(r-1) + v2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[p*c + q].size(); i++)
               ~^~~~~~~~~~~~~~~~~~~~
wombats.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[p*c + q + 1].size(); i++)
               ~^~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[p*c + q].size(); i++)
               ~^~~~~~~~~~~~~~~~~~~~
wombats.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[p*c + q + c].size(); i++)
               ~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12540 KB Output is correct
2 Correct 69 ms 12536 KB Output is correct
3 Execution timed out 20021 ms 15516 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8440 KB Output is correct
2 Correct 12 ms 8440 KB Output is correct
3 Correct 12 ms 8452 KB Output is correct
4 Correct 38 ms 8696 KB Output is correct
5 Correct 22 ms 8568 KB Output is correct
6 Correct 35 ms 8668 KB Output is correct
7 Correct 39 ms 8556 KB Output is correct
8 Correct 35 ms 8440 KB Output is correct
9 Correct 38 ms 8504 KB Output is correct
10 Correct 36 ms 8440 KB Output is correct
11 Correct 13256 ms 10696 KB Output is correct
12 Correct 38 ms 8440 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 9080 KB Output is correct
2 Correct 282 ms 9336 KB Output is correct
3 Correct 240 ms 9208 KB Output is correct
4 Correct 230 ms 9080 KB Output is correct
5 Correct 232 ms 9196 KB Output is correct
6 Correct 12 ms 8440 KB Output is correct
7 Correct 12 ms 8440 KB Output is correct
8 Correct 12 ms 8440 KB Output is correct
9 Correct 259 ms 9216 KB Output is correct
10 Correct 12 ms 8440 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 16676 KB Output is correct
2 Correct 1330 ms 16788 KB Output is correct
3 Correct 671 ms 16920 KB Output is correct
4 Execution timed out 20074 ms 17672 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 9184 KB Output is correct
2 Correct 277 ms 9212 KB Output is correct
3 Correct 232 ms 9208 KB Output is correct
4 Correct 235 ms 9208 KB Output is correct
5 Correct 228 ms 9080 KB Output is correct
6 Correct 652 ms 16704 KB Output is correct
7 Correct 1339 ms 16860 KB Output is correct
8 Correct 651 ms 16804 KB Output is correct
9 Execution timed out 20054 ms 17460 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 9188 KB Output is correct
2 Correct 280 ms 9336 KB Output is correct
3 Correct 232 ms 9208 KB Output is correct
4 Correct 229 ms 9340 KB Output is correct
5 Correct 227 ms 9208 KB Output is correct
6 Correct 648 ms 16796 KB Output is correct
7 Correct 1347 ms 16860 KB Output is correct
8 Correct 647 ms 16632 KB Output is correct
9 Execution timed out 20008 ms 17660 KB Time limit exceeded
10 Halted 0 ms 0 KB -