oj.uz

Submission #28619

# Submission time Handle Problem Language Result Execution time Memory
28619 2017-07-16T08:04:42 Z Official Fan of ACG(#1221, cseteram, 16silver, pps789) Alternative Mart (FXCUP2_mart) C++14
0 / 1
 0 ms 4696 KB 
#include<cstdio>
#include<algorithm>
#include<queue>
#include<functional>
#include<set>
#include<iterator>
using namespace std;

const int INF = 0x3fFFffFF;
const int NMAX = 50000, KMAX = 11;
typedef pair<int, int> pii;
typedef pair<pii, int> tri;
set<pii> dp[NMAX + 1];
vector<pii> g[NMAX + 1];
vector<int> S;

int main() {
	int N, M, K, Q; scanf("%d%d%d%d", &N, &M, &K, &Q);
	for (int i = 0; i < K; i++) {
		int x; scanf("%d", &x); S.push_back(x);
	}

	for (int i = 0; i < M; i++) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({ v,w });
		g[v].push_back({ u,w });
	}

	priority_queue<tri, vector<tri>, greater<tri>> pq;
	for (int s : S) {
		pq.push(tri(pii(0, s), s));
		dp[s].insert(pii(0, s));
	}
	while (!pq.empty()) {
		auto t = pq.top(); pq.pop();
		int here = t.second;
		int cost = t.first.first, from = t.first.second;
		if (dp[here].count({ cost,from })) {
			for (auto edge : g[here]) {
				int there = edge.first, ncost = edge.second + cost;
				pii nstate = { ncost, from };
				bool ok = dp[there].size() < KMAX || nstate < (*dp[there].rbegin());
				for (const auto& p : dp[there]) if (p.second == from) ok = false;
				if (ok) {
					dp[there].insert(nstate);
					if (dp[there].size() > KMAX) dp[there].erase(prev(dp[there].end()));
					pq.push(tri(pii(ncost, from), there));
				}
			}
		}
	}

	for (int q = 0; q < Q; q++) {
		int st, X; scanf("%d%d", &st, &X);
		set<int> fails;
		for (int i = 0; i < X; i++) {
			int f; scanf("%d", &f); fails.insert(f);
		}

		for (const auto& p : dp[st]) if (!fails.count(p.second)) {
			printf("%d %d\n", p.second, p.first); break;
		}
	}
}

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:18:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M, K, Q; scanf("%d%d%d%d", &N, &M, &K, &Q);
                                                   ^
mart.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x); S.push_back(x);
                         ^
mart.cpp:24:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d%d%d", &u, &v, &w);
                                           ^
mart.cpp:54:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int st, X; scanf("%d%d", &st, &X);
                                    ^
mart.cpp:57:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int f; scanf("%d", &f); fails.insert(f);
                          ^

Subtask #1
0 / 1.0

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