oj.uz

Submission #233413

# Submission time Handle Problem Language Result Execution time Memory
233413 2020-05-20T12:49:42 Z crossing0ver Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 1996 ms 69344 KB 
#include<bits/stdc++.h>
#define ll long long 
#define fi first
#define se second
//#include "crocodile.h"
using namespace std;
vector <pair<int,int > > adj[100000];
ll IN[100000][2];
bool vis[100000];
int Ein[100000],v,x;
ll dis[100000],d;
ll val;
struct cmp{
//pair<int,pair<int,int> > a,  b	;
	bool operator() (const  int &a,  const int &b) const {
		if (Ein[a] >= 2 && Ein[b] >= 2)
			return dis[a] <= dis[b];
		return (Ein[a]  >= 2); 
	}
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0; i < M; i++) {
		adj[ R[i][0] ].push_back( { L [i], R[i][1] } );
		adj[ R[i][1] ].push_back( { L[i] , R[i][0] });
	}
	fill(dis,dis + 100000,2000000000000000);
	set<int,cmp>  s;
	for (int i = 0; i < K; i++) 
		Ein[P[i]] = 2,dis[P[i]] = 0,s.insert (P[i]);
	//	cout << s.size() ;
	while (!s.empty()) {
		 v = *s.begin();
		if (Ein[v] < 2) break;   //cout << v <<' ';         
		s.erase(s.begin());
		if (vis[v]) continue;
		vis[v] = 1;
		for (auto i : adj[v]) {
			 x = i.se;
			if (vis[x]) continue;
			s.erase(x);
		   d = i.fi + dis[v];
		   if (IN[x][0] == 0) IN[x][0] = d;
		   else if (IN[x][1] == 0) {
		   	IN[x][1] = d;
		   	if (IN[x][0] > IN[x][1]) swap(IN[x][0],IN[x][1]);
		   }
		   else if (IN[x][1] > d) {
		   	IN[x][1] = d;
		   	if (IN[x][0] > IN[x][1]) swap(IN[x][0],IN[x][1]);
		   }
			s.erase ( x );
			Ein[x] ++;
			if (IN[x][1] && dis[x] > IN[x][1]) {
					dis[x] = IN[x][1];
			}
			s.insert (x);
		}
	}
	return dis[0];	
}   /*  
main() {               int n,m,k;
	cin >> n >> m >> k;
	int R[m][2],L[m]; for(int i = 0; i < m ; i++ )cin >> R[i][0] >> R[i][1] >> L[i];
	  int P[k]; for (int i = 0 ; i < k ; i++) cin >> P[i];
	cout << travel_plan(n,m,R,L,k,P);
			 
}               */
/* 5 4 3
 0 1 2
 0 2 3
 3 2 1
 2 4 4
 1 3 4
 */

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 10 ms 3840 KB Output is correct
10 Correct 7 ms 3456 KB Output is correct
11 Correct 8 ms 3584 KB Output is correct
12 Correct 15 ms 4224 KB Output is correct
13 Correct 14 ms 4480 KB Output is correct
14 Correct 7 ms 3456 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 10 ms 3840 KB Output is correct
10 Correct 7 ms 3456 KB Output is correct
11 Correct 8 ms 3584 KB Output is correct
12 Correct 15 ms 4224 KB Output is correct
13 Correct 14 ms 4480 KB Output is correct
14 Correct 7 ms 3456 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct
16 Incorrect 1996 ms 69344 KB Output isn't correct
17 Halted 0 ms 0 KB -