oj.uz

Submission #26416

# Submission time Handle Problem Language Result Execution time Memory
26416 2017-06-30T04:53:20 Z zscoder Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 211004 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = int(1e9);




const int C = 62;
const int N = 30001*C;
vector<ii> adj[N+30001];
int dist[N+30001];
void addedge(int u, int v, int w)
{
	adj[u].pb(mp(v,w));
}

int getid(int u, int v)
{
	return (u*C+v);
}
set<int> S[30001];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	int s,e;
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		if(i==0) s=x;
		if(i==1) e=x;
		S[x].insert(y);
	}
	for(int i=0;i<n;i++)
	{
		for(sit it = S[i].begin(); it != S[i].end(); it++)
		{
			int y=(*it);
			if(y<C)
			{
				addedge(i+N,getid(i,y),0);
				/*
				if(i-y>=0) 
				{
					addedge(getid(i,y),getid(i-y,y),1);
					//addedge(getid(i,y),i-y+N,1);
				}
				if(i+y<n) 
				{
					addedge(getid(i,y),getid(i+y,y),1);
					//addedge(getid(i,y),i+y+N,1);
				}
				*/
			}
			else
			{
				int cnt=0;
				for(int j=i+y;j<n;j+=y)
				{
					addedge(i+N,j+N,++cnt);
				}
				cnt=0;
				for(int j=i-y;j>=0;j-=y)
				{
					addedge(i+N,j+N,++cnt);
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<C;j++)
		{
			if(i-j>=0) 
			{
				addedge(getid(i,j),i-j+N,1);
				addedge(getid(i,j),getid(i-j,j),1);
			}
			if(i+j<n) 
			{
				addedge(getid(i,j),getid(i+j,j),1);
				addedge(getid(i,j),i+j+N,1);
			}
		}
	}
	e+=N;
	s+=N;
	priority_queue<ii,vector<ii>,greater<ii> > pq;
	for(int i=0;i<N+30001;i++) dist[i]=INF;
	pq.push(mp(0,s));
	dist[s]=0;
	while(!pq.empty())
	{
		int d = pq.top().fi; int u = pq.top().se; pq.pop();
		//cerr<<d<<' '<<u<<'\n';
		for(int i=0;i<adj[u].size();i++)
		{
			int v=adj[u][i].fi; int w=adj[u][i].se;
			if(d+w<dist[v])
			{
				dist[v]=d+w;
				pq.push(mp(dist[v],v));
			}
		}
	}
	if(dist[e]>=INF) dist[e]=-1;
	cout<<dist[e]<<'\n';
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[u].size();i++)
                ^
skyscraper.cpp:109:6: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  s+=N;
      ^
skyscraper.cpp:108:6: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  e+=N;
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55272 KB Output is correct
2 Correct 16 ms 55272 KB Output is correct
3 Correct 13 ms 55272 KB Output is correct
4 Correct 6 ms 55272 KB Output is correct
5 Correct 9 ms 55272 KB Output is correct
6 Correct 13 ms 55272 KB Output is correct
7 Correct 9 ms 55272 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 55272 KB Output is correct
2 Correct 9 ms 55272 KB Output is correct
3 Correct 3 ms 55272 KB Output is correct
4 Correct 9 ms 55272 KB Output is correct
5 Correct 9 ms 55272 KB Output is correct
6 Correct 6 ms 55272 KB Output is correct
7 Correct 9 ms 55272 KB Output is correct
8 Correct 9 ms 55272 KB Output is correct
9 Correct 19 ms 55272 KB Output is correct
10 Correct 13 ms 55536 KB Output is correct
11 Correct 9 ms 55536 KB Output is correct
12 Correct 9 ms 55404 KB Output is correct
13 Correct 13 ms 55536 KB Output is correct
14 Correct 23 ms 55676 KB Output is correct
15 Correct 13 ms 55676 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 55272 KB Output is correct
2 Correct 9 ms 55272 KB Output is correct
3 Correct 6 ms 55272 KB Output is correct
4 Correct 9 ms 55272 KB Output is correct
5 Correct 6 ms 55272 KB Output is correct
6 Correct 16 ms 55272 KB Output is correct
7 Correct 13 ms 55272 KB Output is correct
8 Correct 6 ms 55272 KB Output is correct
9 Correct 9 ms 55272 KB Output is correct
10 Correct 13 ms 55536 KB Output is correct
11 Correct 9 ms 55536 KB Output is correct
12 Correct 6 ms 55404 KB Output is correct
13 Correct 9 ms 55536 KB Output is correct
14 Correct 13 ms 55676 KB Output is correct
15 Correct 13 ms 55676 KB Output is correct
16 Correct 13 ms 55800 KB Output is correct
17 Correct 19 ms 57516 KB Output is correct
18 Correct 33 ms 60288 KB Output is correct
19 Correct 26 ms 60948 KB Output is correct
20 Correct 33 ms 61080 KB Output is correct
21 Correct 19 ms 56328 KB Output is correct
22 Correct 39 ms 60288 KB Output is correct
23 Correct 33 ms 59892 KB Output is correct
24 Correct 33 ms 60816 KB Output is correct
25 Correct 43 ms 61080 KB Output is correct
26 Correct 36 ms 60948 KB Output is correct
27 Correct 36 ms 60948 KB Output is correct
28 Correct 29 ms 61080 KB Output is correct
29 Correct 49 ms 60948 KB Output is correct
30 Correct 33 ms 60948 KB Output is correct
31 Correct 39 ms 60948 KB Output is correct
32 Correct 33 ms 60948 KB Output is correct
33 Correct 66 ms 61268 KB Output is correct
34 Correct 59 ms 61268 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55272 KB Output is correct
2 Correct 13 ms 55272 KB Output is correct
3 Correct 19 ms 55272 KB Output is correct
4 Correct 13 ms 55272 KB Output is correct
5 Correct 13 ms 55272 KB Output is correct
6 Correct 13 ms 55272 KB Output is correct
7 Correct 9 ms 55272 KB Output is correct
8 Correct 23 ms 55272 KB Output is correct
9 Correct 13 ms 55272 KB Output is correct
10 Correct 13 ms 55536 KB Output is correct
11 Correct 19 ms 55536 KB Output is correct
12 Correct 16 ms 55404 KB Output is correct
13 Correct 13 ms 55536 KB Output is correct
14 Correct 13 ms 55676 KB Output is correct
15 Correct 13 ms 55676 KB Output is correct
16 Correct 19 ms 55800 KB Output is correct
17 Correct 23 ms 57516 KB Output is correct
18 Correct 26 ms 60288 KB Output is correct
19 Correct 33 ms 60948 KB Output is correct
20 Correct 26 ms 61080 KB Output is correct
21 Correct 9 ms 56328 KB Output is correct
22 Correct 29 ms 60288 KB Output is correct
23 Correct 33 ms 59892 KB Output is correct
24 Correct 46 ms 60816 KB Output is correct
25 Correct 46 ms 61080 KB Output is correct
26 Correct 39 ms 60948 KB Output is correct
27 Correct 33 ms 60948 KB Output is correct
28 Correct 26 ms 61080 KB Output is correct
29 Correct 46 ms 60948 KB Output is correct
30 Correct 39 ms 60948 KB Output is correct
31 Correct 36 ms 60948 KB Output is correct
32 Correct 43 ms 60948 KB Output is correct
33 Correct 56 ms 61268 KB Output is correct
34 Correct 69 ms 61268 KB Output is correct
35 Correct 59 ms 61104 KB Output is correct
36 Correct 29 ms 58572 KB Output is correct
37 Correct 53 ms 62796 KB Output is correct
38 Correct 73 ms 63328 KB Output is correct
39 Correct 86 ms 63324 KB Output is correct
40 Correct 79 ms 63348 KB Output is correct
41 Correct 69 ms 63344 KB Output is correct
42 Correct 43 ms 60948 KB Output is correct
43 Correct 46 ms 60948 KB Output is correct
44 Correct 29 ms 61080 KB Output is correct
45 Correct 79 ms 66480 KB Output is correct
46 Correct 89 ms 66480 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55272 KB Output is correct
2 Correct 6 ms 55272 KB Output is correct
3 Correct 9 ms 55272 KB Output is correct
4 Correct 6 ms 55272 KB Output is correct
5 Correct 16 ms 55272 KB Output is correct
6 Correct 23 ms 55272 KB Output is correct
7 Correct 9 ms 55272 KB Output is correct
8 Correct 16 ms 55272 KB Output is correct
9 Correct 6 ms 55272 KB Output is correct
10 Correct 16 ms 55536 KB Output is correct
11 Correct 16 ms 55536 KB Output is correct
12 Correct 9 ms 55404 KB Output is correct
13 Correct 23 ms 55536 KB Output is correct
14 Correct 16 ms 55676 KB Output is correct
15 Correct 13 ms 55676 KB Output is correct
16 Correct 19 ms 55800 KB Output is correct
17 Correct 26 ms 57516 KB Output is correct
18 Correct 26 ms 60288 KB Output is correct
19 Correct 36 ms 60948 KB Output is correct
20 Correct 29 ms 61080 KB Output is correct
21 Correct 16 ms 56328 KB Output is correct
22 Correct 26 ms 60288 KB Output is correct
23 Correct 36 ms 59892 KB Output is correct
24 Correct 33 ms 60816 KB Output is correct
25 Correct 46 ms 61080 KB Output is correct
26 Correct 26 ms 60948 KB Output is correct
27 Correct 33 ms 60948 KB Output is correct
28 Correct 33 ms 61080 KB Output is correct
29 Correct 53 ms 60948 KB Output is correct
30 Correct 26 ms 60948 KB Output is correct
31 Correct 39 ms 60948 KB Output is correct
32 Correct 46 ms 60948 KB Output is correct
33 Correct 56 ms 61268 KB Output is correct
34 Correct 63 ms 61268 KB Output is correct
35 Correct 39 ms 61104 KB Output is correct
36 Correct 29 ms 58572 KB Output is correct
37 Correct 83 ms 62796 KB Output is correct
38 Correct 79 ms 63328 KB Output is correct
39 Correct 66 ms 63324 KB Output is correct
40 Correct 76 ms 63348 KB Output is correct
41 Correct 73 ms 63344 KB Output is correct
42 Correct 36 ms 60948 KB Output is correct
43 Correct 46 ms 60948 KB Output is correct
44 Correct 33 ms 61080 KB Output is correct
45 Correct 96 ms 66480 KB Output is correct
46 Correct 89 ms 66480 KB Output is correct
47 Correct 323 ms 97132 KB Output is correct
48 Correct 309 ms 124044 KB Output is correct
49 Correct 299 ms 129852 KB Output is correct
50 Correct 383 ms 136584 KB Output is correct
51 Correct 486 ms 144764 KB Output is correct
52 Correct 476 ms 144880 KB Output is correct
53 Correct 369 ms 142524 KB Output is correct
54 Correct 316 ms 140940 KB Output is correct
55 Correct 343 ms 140940 KB Output is correct
56 Correct 319 ms 143316 KB Output is correct
57 Correct 503 ms 141204 KB Output is correct
58 Correct 369 ms 140940 KB Output is correct
59 Correct 376 ms 140940 KB Output is correct
60 Correct 389 ms 141468 KB Output is correct
61 Correct 379 ms 141336 KB Output is correct
62 Correct 443 ms 145296 KB Output is correct
63 Correct 386 ms 168056 KB Output is correct
64 Correct 459 ms 178500 KB Output is correct
65 Correct 399 ms 194316 KB Output is correct
66 Execution timed out 1000 ms 211004 KB Execution timed out
67 Halted 0 ms 0 KB -