Submission #43932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
43932	2018-03-28T10:55:45 Z	Kerim	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1000 ms	262144 KB

skyscraper

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define BLOK 300
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
PII arr[MAXN];
int dis[MAXN];
vector<PII>adj[MAXN];
int s,t;
bool vis[30009][BLOK+5];
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		if(i==1)
			s=u;
		if(i==2)
			t=u;
		arr[i]=mp(u,v);	
	}
	sort(arr+1,arr+m+1);
	for(int i=m;i>=1;i--){
		int cur=1;
		int u=arr[i].ff,v=arr[i].ss;
		for(int j=u+v;j<n;j+=v){
			adj[u].pb(mp(j,cur));
			if(v<BLOK and vis[j][v])
				break;
			//might be break condition
			cur++;
		}
		if(v<BLOK)
			vis[u][v]=1;
	}memset(vis,0,sizeof vis);
	for(int i=1;i<=m;i++){
		int cur=1;
		int u=arr[i].ff,v=arr[i].ss;
		for(int j=u-v;j>=0;j-=v){
			adj[u].pb(mp(j,cur));
			if(v<BLOK and vis[j][v])
				break;
			//might be break condition
			cur++;
		}
		if(v<BLOK)
			vis[u][v]=1;
	}
	priority_queue<pair<int,int> >q;
	q.push(mp(0,s));
	for(int i=0;i<n;i++)
		dis[i]=INF;
	dis[s]=0;
	while(!q.empty()){
		int val=-q.top().ff;
		int nd=q.top().ss;
		q.pop();
		if(dis[nd]!=val)
			continue;
		tr(it,adj[nd])
			if(umin(dis[it->ff],dis[nd]+it->ss))
				q.push(mp(-dis[it->ff],it->ff));
	}
	if(dis[t]==INF)
		dis[t]=-1;
	printf("%d\n",dis[t]);
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	11640 KB	Output is correct
2	Correct	10 ms	11640 KB	Output is correct
3	Correct	10 ms	11840 KB	Output is correct
4	Correct	10 ms	11840 KB	Output is correct
5	Correct	10 ms	11840 KB	Output is correct
6	Correct	10 ms	11840 KB	Output is correct
7	Correct	9 ms	11840 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	11840 KB	Output is correct
2	Correct	10 ms	11840 KB	Output is correct
3	Correct	10 ms	11876 KB	Output is correct
4	Correct	10 ms	11876 KB	Output is correct
5	Correct	11 ms	11876 KB	Output is correct
6	Correct	12 ms	11876 KB	Output is correct
7	Correct	12 ms	11884 KB	Output is correct
8	Correct	11 ms	11884 KB	Output is correct
9	Correct	10 ms	11884 KB	Output is correct
10	Correct	10 ms	11884 KB	Output is correct
11	Correct	11 ms	11884 KB	Output is correct
12	Correct	15 ms	14036 KB	Output is correct
13	Correct	10 ms	14036 KB	Output is correct
14	Correct	11 ms	14036 KB	Output is correct
15	Correct	10 ms	14036 KB	Output is correct

Subtask #3

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14036 KB	Output is correct
2	Correct	10 ms	14036 KB	Output is correct
3	Correct	10 ms	14036 KB	Output is correct
4	Correct	10 ms	14036 KB	Output is correct
5	Correct	11 ms	14036 KB	Output is correct
6	Correct	10 ms	14036 KB	Output is correct
7	Correct	10 ms	14036 KB	Output is correct
8	Correct	11 ms	14036 KB	Output is correct
9	Correct	10 ms	14036 KB	Output is correct
10	Correct	10 ms	14036 KB	Output is correct
11	Correct	11 ms	14036 KB	Output is correct
12	Correct	15 ms	14048 KB	Output is correct
13	Correct	11 ms	14048 KB	Output is correct
14	Correct	11 ms	14048 KB	Output is correct
15	Correct	11 ms	14048 KB	Output is correct
16	Correct	10 ms	14048 KB	Output is correct
17	Correct	12 ms	14048 KB	Output is correct
18	Correct	10 ms	14048 KB	Output is correct
19	Correct	10 ms	14048 KB	Output is correct
20	Correct	11 ms	14048 KB	Output is correct
21	Correct	11 ms	14048 KB	Output is correct
22	Correct	10 ms	14048 KB	Output is correct
23	Correct	11 ms	14048 KB	Output is correct
24	Correct	11 ms	14048 KB	Output is correct
25	Correct	11 ms	14048 KB	Output is correct
26	Correct	95 ms	44864 KB	Output is correct
27	Correct	90 ms	44864 KB	Output is correct
28	Correct	12 ms	44864 KB	Output is correct
29	Correct	13 ms	44864 KB	Output is correct
30	Correct	11 ms	44864 KB	Output is correct
31	Correct	13 ms	44864 KB	Output is correct
32	Correct	11 ms	44864 KB	Output is correct
33	Correct	14 ms	44864 KB	Output is correct
34	Correct	13 ms	44864 KB	Output is correct

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	44864 KB	Output is correct
2	Correct	10 ms	44864 KB	Output is correct
3	Correct	10 ms	44864 KB	Output is correct
4	Correct	10 ms	44864 KB	Output is correct
5	Correct	10 ms	44864 KB	Output is correct
6	Correct	10 ms	44864 KB	Output is correct
7	Correct	10 ms	44864 KB	Output is correct
8	Correct	10 ms	44864 KB	Output is correct
9	Correct	10 ms	44864 KB	Output is correct
10	Correct	10 ms	44864 KB	Output is correct
11	Correct	11 ms	44864 KB	Output is correct
12	Correct	14 ms	44864 KB	Output is correct
13	Correct	10 ms	44864 KB	Output is correct
14	Correct	13 ms	44864 KB	Output is correct
15	Correct	11 ms	44864 KB	Output is correct
16	Correct	10 ms	44864 KB	Output is correct
17	Correct	11 ms	44864 KB	Output is correct
18	Correct	11 ms	44864 KB	Output is correct
19	Correct	10 ms	44864 KB	Output is correct
20	Correct	10 ms	44864 KB	Output is correct
21	Correct	10 ms	44864 KB	Output is correct
22	Correct	10 ms	44864 KB	Output is correct
23	Correct	11 ms	44864 KB	Output is correct
24	Correct	11 ms	44864 KB	Output is correct
25	Correct	12 ms	44864 KB	Output is correct
26	Correct	95 ms	44880 KB	Output is correct
27	Correct	89 ms	44880 KB	Output is correct
28	Correct	12 ms	44880 KB	Output is correct
29	Correct	12 ms	44880 KB	Output is correct
30	Correct	11 ms	44880 KB	Output is correct
31	Correct	11 ms	44880 KB	Output is correct
32	Correct	11 ms	44880 KB	Output is correct
33	Correct	14 ms	44880 KB	Output is correct
34	Correct	14 ms	44880 KB	Output is correct
35	Correct	28 ms	44880 KB	Output is correct
36	Correct	13 ms	44880 KB	Output is correct
37	Correct	23 ms	44880 KB	Output is correct
38	Correct	26 ms	44880 KB	Output is correct
39	Correct	25 ms	44880 KB	Output is correct
40	Correct	26 ms	44880 KB	Output is correct
41	Correct	26 ms	44880 KB	Output is correct
42	Execution timed out	1100 ms	262144 KB	Time limit exceeded
43	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	262144 KB	Output is correct
2	Correct	12 ms	262144 KB	Output is correct
3	Correct	9 ms	262144 KB	Output is correct
4	Correct	9 ms	262144 KB	Output is correct
5	Correct	10 ms	262144 KB	Output is correct
6	Correct	9 ms	262144 KB	Output is correct
7	Correct	10 ms	262144 KB	Output is correct
8	Correct	10 ms	262144 KB	Output is correct
9	Correct	10 ms	262144 KB	Output is correct
10	Correct	10 ms	262144 KB	Output is correct
11	Correct	11 ms	262144 KB	Output is correct
12	Correct	14 ms	262144 KB	Output is correct
13	Correct	18 ms	262144 KB	Output is correct
14	Correct	10 ms	262144 KB	Output is correct
15	Correct	10 ms	262144 KB	Output is correct
16	Correct	10 ms	262144 KB	Output is correct
17	Correct	11 ms	262144 KB	Output is correct
18	Correct	11 ms	262144 KB	Output is correct
19	Correct	10 ms	262144 KB	Output is correct
20	Correct	11 ms	262144 KB	Output is correct
21	Correct	10 ms	262144 KB	Output is correct
22	Correct	10 ms	262144 KB	Output is correct
23	Correct	11 ms	262144 KB	Output is correct
24	Correct	12 ms	262144 KB	Output is correct
25	Correct	12 ms	262144 KB	Output is correct
26	Correct	94 ms	262144 KB	Output is correct
27	Correct	90 ms	262144 KB	Output is correct
28	Correct	13 ms	262144 KB	Output is correct
29	Correct	12 ms	262144 KB	Output is correct
30	Correct	11 ms	262144 KB	Output is correct
31	Correct	11 ms	262144 KB	Output is correct
32	Correct	12 ms	262144 KB	Output is correct
33	Correct	14 ms	262144 KB	Output is correct
34	Correct	13 ms	262144 KB	Output is correct
35	Correct	22 ms	262144 KB	Output is correct
36	Correct	12 ms	262144 KB	Output is correct
37	Correct	27 ms	262144 KB	Output is correct
38	Correct	27 ms	262144 KB	Output is correct
39	Correct	27 ms	262144 KB	Output is correct
40	Correct	31 ms	262144 KB	Output is correct
41	Correct	26 ms	262144 KB	Output is correct
42	Execution timed out	1108 ms	262144 KB	Time limit exceeded
43	Halted	0 ms	0 KB	-