oj.uz

답안 #443841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443841 2021-07-12T08:31:48 Z IvanJ 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 2000 ms 2636 KB 
#include<bits/stdc++.h>
#include "crocodile.h"

#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;
const ll inf = 1e18;

int n, m, k;
vector<pair<int, ll>> adj[maxn];
int E[maxn];
pair<ll, ll> dist[maxn];

int solve() {
	set<pair<pair<ll, ll>, int>> s;
	for(int i = 0;i < n;i++) dist[i] = {inf, inf}, s.insert({dist[i], i});
	for(int i = 0;i < n;i++) {
		if(!E[i]) continue;
		dist[i] = {0, 0};
		s.erase({{inf, inf}, i});
		s.insert({dist[i], i});
	}
	
	for(int i = 0;i < n;i++) {
		//for(auto p : s) cout << "(" << p.y << " | " << p.x.x << " " << p.x.y << ")\n";
		pair<pair<ll, ll>, int> state = *s.begin();s.erase(s.begin());
		int x = state.y;
		pair<ll, ll> d = state.x;
		//cout << x << " -> " << d.x << ' ' << d.y << "\n";
		//cout << "\n";
		for(pair<int, ll> p : adj[x]) {
			if(s.find({dist[p.x], p.x}) != s.end())
				s.erase({dist[p.x], p.x});
			pair<ll, ll> di = dist[p.x];
			if(d.y + p.y < dist[p.x].y) {
				dist[p.x].x = dist[p.x].y;
				dist[p.x].y = d.y + p.y;
			} else if(d.x + p.y < dist[p.x].x) {
				dist[p.x].x = d.x + p.y;
			}
			if(di != dist[p.x]) s.insert({dist[p.x], p.x});
		}
	}

	return (int)dist[0].x;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  n = N, m = M, k = K;
  for(int i = 0;i < m;i++) {
	  adj[R[i][0]].pb({R[i][1], L[i]});
	  adj[R[i][1]].pb({R[i][0], L[i]});
  }
  for(int i = 0;i < k;i++) E[P[i]] = 1;
  
  return solve();
}

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2088 ms 2636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2088 ms 2636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2088 ms 2636 KB Time limit exceeded
2 Halted 0 ms 0 KB -