oj.uz

Submission #133867

# Submission time Handle Problem Language Result Execution time Memory
133867 2019-07-21T15:43:40 Z arthurconmy Wombats (IOI13_wombats) C++14
12 / 100
 90 ms 15992 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];
int ans[20][20];
vector<pii> adj[400];
int dis[400];

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];
		}
	}

	// pre-calculate all the answers
	// Floyd-Warshall on a directed graph

	for(int i=0; i<=400; 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]));
		}
	}

	for(int i=0; i<400; i++) dis[i]=INF;

	for(int u=0; u<c; u++)
	{
		// dis[u]=0;
		priority_queue<pii> PQ;
		PQ.push(make_pair(-0,u));

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

			if(dis[v]!=INF) continue;
			dis[v]=cur_dis;

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

				if(dis[w]==INF)
				{
					//dis[w]=cur_dis+jump;
					//cout << w << " " << dis[w] << endl;
					PQ.push(make_pair(-cur_dis-jump,w));
				}
			}
		}

		for(int i=0; i<r*c; i++)
		{
			if(int(i/c)==r-1)
			{
				// cout << u << " " << i%c << " " << dis[i] << endl;
				ans[u][i%c]=dis[i];
			}
		}

		for(int i=0; i<400; i++) dis[i]=INF;
	}
}

#ifndef ARTHUR_LOCAL
	void changeH(int p, int q, int w)
	{
		return;
	}

	void changeV(int p, int q, int w)
	{
		return;
	}
#endif

int escape(int v1, int v2)
{
	return ans[v1][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;
      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12024 KB Output is correct
2 Incorrect 14 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8184 KB Output is correct
2 Correct 11 ms 8184 KB Output is correct
3 Correct 12 ms 8184 KB Output is correct
4 Correct 13 ms 8312 KB Output is correct
5 Correct 12 ms 8312 KB Output is correct
6 Correct 13 ms 8312 KB Output is correct
7 Correct 13 ms 8184 KB Output is correct
8 Correct 13 ms 8184 KB Output is correct
9 Correct 13 ms 8248 KB Output is correct
10 Correct 15 ms 8188 KB Output is correct
11 Correct 90 ms 10608 KB Output is correct
12 Correct 14 ms 8268 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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