oj.uz

Submission #302661

# Submission time Handle Problem Language Result Execution time Memory
302661 2020-09-19T02:42:32 Z shrek12357 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 3 ms 2688 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include "crocodile.h"
using namespace std;
 
const long long INF = 1e10;
const int MAXN = 1e5+5;
 
bool ex[MAXN];
vector<pair<int, int>> adjList[MAXN];
int n, m, k;
long long dp[MAXN];
 
void dfs(int src, set<int> par) {
	int cur = adjList[src].size();
	if (src != 0) {
		cur -= par.size();
	}
	if (ex[src]) {
		dp[src] = 0;
		return;
	}
	if (cur < 2) {
		return;
	}
	long long t1 = 5*INF, t2 = 5*INF;
	for (auto i : adjList[src]) {
		if (par.find(i.first) != par.end()) {
			continue;
		}
		set<int> temp = par;
		temp.insert(src);
		dfs(i.first, temp);
		if (dp[i.first] + i.second < t1) {
			t2 = t1;
			t1 = dp[i.first] + i.second;
		}
		else if (dp[i.first] + i.second < t2) {
			t2 = dp[i.first] + i.second;
		}
	}
	dp[src] = t2;
}
 
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 < k; i++) {
		ex[p[i]] = true;
	}
	for (int i = 0; i < m; i++) {
		adjList[r[i][0]].push_back({ r[i][1], l[i] });
		adjList[r[i][1]].push_back({ r[i][0], l[i] });
	}
	for (int i = 0; i < n; i++) {
		dp[i] = INF;
	}
	set<int> temp;
	temp.insert(0);
	dfs(0, temp);
	return (int)dp[0];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Incorrect 3 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Incorrect 3 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Incorrect 3 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -