| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 28404 | 2017-07-16T05:20:38 Z | AcornCkiGuiziTeam(#1202, dotorya, cki86201, zigui) | Alternative Mart (FXCUP2_mart) | C++14 | 3946 ms | 50972 KB |
#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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 5788 KB | Output is correct |
| 2 | Correct | 0 ms | 5788 KB | Output is correct |
| 3 | Correct | 0 ms | 5788 KB | Output is correct |
| 4 | Correct | 0 ms | 5788 KB | Output is correct |
| 5 | Correct | 3 ms | 5788 KB | Output is correct |
| 6 | Correct | 0 ms | 5788 KB | Output is correct |
| 7 | Correct | 3 ms | 6052 KB | Output is correct |
| 8 | Correct | 3 ms | 6052 KB | Output is correct |
| 9 | Correct | 146 ms | 11080 KB | Output is correct |
| 10 | Correct | 19 ms | 6596 KB | Output is correct |
| 11 | Correct | 56 ms | 8728 KB | Output is correct |
| 12 | Correct | 43 ms | 8560 KB | Output is correct |
| 13 | Correct | 1936 ms | 47164 KB | Output is correct |
| 14 | Correct | 1923 ms | 47168 KB | Output is correct |
| 15 | Correct | 99 ms | 10084 KB | Output is correct |
| 16 | Correct | 99 ms | 9748 KB | Output is correct |
| 17 | Correct | 1096 ms | 31908 KB | Output is correct |
| 18 | Correct | 739 ms | 30868 KB | Output is correct |
| 19 | Correct | 1209 ms | 35048 KB | Output is correct |
| 20 | Correct | 1012 ms | 33112 KB | Output is correct |
| 21 | Correct | 1399 ms | 35056 KB | Output is correct |
| 22 | Correct | 1383 ms | 33188 KB | Output is correct |
| 23 | Correct | 1666 ms | 36488 KB | Output is correct |
| 24 | Correct | 1829 ms | 34660 KB | Output is correct |
| 25 | Correct | 1873 ms | 36488 KB | Output is correct |
| 26 | Correct | 1823 ms | 34660 KB | Output is correct |
| 27 | Correct | 126 ms | 10580 KB | Output is correct |
| 28 | Correct | 123 ms | 10292 KB | Output is correct |
| 29 | Correct | 1599 ms | 33024 KB | Output is correct |
| 30 | Correct | 1336 ms | 31836 KB | Output is correct |
| 31 | Correct | 2136 ms | 36652 KB | Output is correct |
| 32 | Correct | 1096 ms | 34068 KB | Output is correct |
| 33 | Correct | 1719 ms | 36632 KB | Output is correct |
| 34 | Correct | 3013 ms | 40052 KB | Output is correct |
| 35 | Correct | 2296 ms | 39720 KB | Output is correct |
| 36 | Correct | 2863 ms | 39856 KB | Output is correct |
| 37 | Correct | 3389 ms | 40052 KB | Output is correct |
| 38 | Correct | 2956 ms | 39932 KB | Output is correct |
| 39 | Correct | 149 ms | 11104 KB | Output is correct |
| 40 | Correct | 153 ms | 11132 KB | Output is correct |
| 41 | Correct | 2086 ms | 34908 KB | Output is correct |
| 42 | Correct | 2029 ms | 34940 KB | Output is correct |
| 43 | Correct | 3429 ms | 40356 KB | Output is correct |
| 44 | Correct | 3586 ms | 40252 KB | Output is correct |
| 45 | Correct | 3679 ms | 40316 KB | Output is correct |
| 46 | Correct | 3509 ms | 40300 KB | Output is correct |
| 47 | Correct | 3749 ms | 49124 KB | Output is correct |
| 48 | Correct | 3836 ms | 50844 KB | Output is correct |
| 49 | Correct | 3933 ms | 49128 KB | Output is correct |
| 50 | Correct | 3946 ms | 50708 KB | Output is correct |
| 51 | Correct | 3433 ms | 49524 KB | Output is correct |
| 52 | Correct | 3459 ms | 50972 KB | Output is correct |
| 53 | Correct | 393 ms | 33112 KB | Output is correct |
| 54 | Correct | 2689 ms | 36908 KB | Output is correct |
| 55 | Correct | 2796 ms | 39988 KB | Output is correct |
| 56 | Correct | 3633 ms | 40328 KB | Output is correct |
| 57 | Correct | 763 ms | 18200 KB | Output is correct |