Submission #28404

#	Time	Username	Problem	Language	Result	Execution time	Memory
28404		AcornCkiGuiziTeam (#68)	Alternative Mart (FXCUP2_mart)	C++14	1 / 1	3946 ms	50972 KiB

mart

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:1048576")  
using namespace std;

#define mp make_pair  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef tuple <int, int, int> t3;

int IT_MAX = 1 << 17;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)

vector <pii> conn[50050];
set<pii> dis[50050];
int dchk[50050];
bool chk[50050];
int main() {
	int N, M, K, Q, i;
	scanf("%d %d %d %d", &N, &M, &K, &Q);
	for (i = 1; i <= K; i++) {
		int t;
		scanf("%d", &t);
		chk[t] = true;
	}
	for (i = 1; i <= M; i++) {
		int t1, t2, t3;
		scanf("%d %d %d", &t1, &t2, &t3);
		conn[t1].emplace_back(t3, t2);
		conn[t2].emplace_back(t3, t1);
	}

	priority_queue <pair<pii, int>, vector<pair<pii, int>>, greater<pair<pii, int>>> Hx;
	for (i = 1; i <= N; i++) {
		if (!chk[i]) continue;
		dis[i].insert(pii(0, i));
		Hx.emplace(pii(0, i), i);
	}
	while (!Hx.empty()) {
		auto u = Hx.top();
		Hx.pop();
		pii d = u.first;
		int p = u.second;
		if (dis[p].find(d) == dis[p].end()) continue;
		for (pii c : conn[p]) {
			pii q = pii(d.first + c.first, d.second);
			int r = c.second;
			int ch = 1;
			for (pii x : dis[r]) {
				if (q.second == x.second) {
					if (q.first < x.first) {
						dis[r].erase(dis[r].find(x));
					}
					else ch = 0;
					break;
				}
			}
			if (ch) {
				dis[r].insert(q);
				Hx.emplace(q, r);
			}
			if (dis[r].size() >= 12) dis[r].erase(--dis[r].end());
		}
	}

	for (i = 1; i <= N; i++) dchk[i] = 0;
	for(int q = 1; q <= Q; q++) {
		int S, X, i, t;
		scanf("%d %d", &S, &X);
		while (X--) {
			scanf("%d", &t);
			dchk[t] = q;
		}
		for (auto it : dis[S]) if (dchk[it.second] != q) {
			printf("%d %d\n", it.second, it.first);
			break;
		}
	}
	return 0;
}

Compilation message (stderr)

mart.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
mart.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:1048576")  
 ^
mart.cpp: In function 'int main()':
mart.cpp:104:13: warning: unused variable 'i' [-Wunused-variable]
   int S, X, i, t;
             ^
mart.cpp:56:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &N, &M, &K, &Q);
                                      ^
mart.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
                  ^
mart.cpp:64:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t1, &t2, &t3);
                                   ^
mart.cpp:105:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &S, &X);
                         ^
mart.cpp:107:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &t);
                   ^

• Subtask 1: 1 / 1