oj.uz

Submission #88011

# Submission time Handle Problem Language Result Execution time Memory
88011 2018-12-03T11:21:03 Z Pajaraja Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1522 ms 106532 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > g[100007];
int cnt[100007],d[100007];
int travel_plan(int N, int M,int R[][2],int L[],int K,int P[]) 
{
	fill(d,d+100007,-1);
	for(int i=0;i<M;i++)
	{
		pair<int,int> p=make_pair(-L[i],R[i][0]);
		g[R[i][1]].push_back(p);
		p.second=R[i][1];
		g[R[i][0]].push_back(p);
	}
	priority_queue<pair<int,int> > q;
	for(int i=0;i<K;i++) 
	{
	    for(int j=0;j<g[P[i]].size();j++) q.push(g[P[i]][j]);
	    d[P[i]]=0;
	}
	while(!q.empty())
	{
		pair<int,int> p=q.top();
		q.pop();
		if(d[p.second]!=-1) continue;
		cnt[p.second]++;
		if(cnt[p.second]==2)
		{
			d[p.second]=p.first;
			for(int i=0;i<g[p.second].size();i++)
			{
				pair<int,int> r=g[p.second][i];
				r.first+=p.first;
				q.push(r);
			}
		}
	}
	return -d[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=0;j<g[P[i]].size();j++) q.push(g[P[i]][j]);
                  ~^~~~~~~~~~~~~~~
crocodile.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<g[p.second].size();i++)
                ~^~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3072 KB Output is correct
3 Correct 5 ms 3248 KB Output is correct
4 Correct 5 ms 3364 KB Output is correct
5 Correct 5 ms 3396 KB Output is correct
6 Correct 0 ms 3428 KB Output is correct
7 Correct 6 ms 3644 KB Output is correct
8 Correct 6 ms 3652 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3072 KB Output is correct
3 Correct 5 ms 3248 KB Output is correct
4 Correct 5 ms 3364 KB Output is correct
5 Correct 5 ms 3396 KB Output is correct
6 Correct 0 ms 3428 KB Output is correct
7 Correct 6 ms 3644 KB Output is correct
8 Correct 6 ms 3652 KB Output is correct
9 Correct 8 ms 4052 KB Output is correct
10 Correct 5 ms 4052 KB Output is correct
11 Correct 4 ms 4052 KB Output is correct
12 Correct 12 ms 4548 KB Output is correct
13 Correct 11 ms 4792 KB Output is correct
14 Correct 6 ms 4792 KB Output is correct
15 Correct 6 ms 4792 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 3072 KB Output is correct
3 Correct 5 ms 3248 KB Output is correct
4 Correct 5 ms 3364 KB Output is correct
5 Correct 5 ms 3396 KB Output is correct
6 Correct 0 ms 3428 KB Output is correct
7 Correct 6 ms 3644 KB Output is correct
8 Correct 6 ms 3652 KB Output is correct
9 Correct 8 ms 4052 KB Output is correct
10 Correct 5 ms 4052 KB Output is correct
11 Correct 4 ms 4052 KB Output is correct
12 Correct 12 ms 4548 KB Output is correct
13 Correct 11 ms 4792 KB Output is correct
14 Correct 6 ms 4792 KB Output is correct
15 Correct 6 ms 4792 KB Output is correct
16 Correct 1306 ms 73592 KB Output is correct
17 Correct 125 ms 73592 KB Output is correct
18 Correct 164 ms 73592 KB Output is correct
19 Correct 1522 ms 99276 KB Output is correct
20 Correct 880 ms 106532 KB Output is correct
21 Correct 63 ms 106532 KB Output is correct
22 Correct 712 ms 106532 KB Output is correct