| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 29083 | 2017-07-18T08:11:41 Z | cki86201 | Alternative Mart (FXCUP2_mart) | C++11 | 1293 ms | 44012 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;
int n, m, k, q;
vector <int> mart;
vector <pii> E[50050];
vector <pii> M[50050];
void solve() {
scanf("%d%d%d%d", &n, &m, &k, &q);
rep(i, k) {
int x; scanf("%d", &x);
mart.pb(x);
}
rep(i, m) {
int x, y, z; scanf("%d%d%d", &x, &y, &z);
E[x].pb(pii(z, y));
E[y].pb(pii(z, x));
}
priority_queue <t3, vector<t3>, greater<t3> > pq;
for(int e : mart) {
M[e].pb(pii(0, e));
pq.push(t3(0, e, e));
}
while(!pq.empty()) {
t3 t = pq.top(); pq.pop();
int v = get<1>(t), s = get<2>(t);
int L = get<0>(t);
int ok = 0;
for(pii e : M[v]) if(e.Fi == L && e.Se == s){ ok = 1; break; }
if(ok == 0) continue;
for(pii e : E[v]) {
int flag = 0;
for(pii &f : M[e.Se]) if(f.Se == s) {
flag = 1;
if(f.Fi > L + e.Fi) {
f.Fi = L + e.Fi;
pq.push(t3(L + e.Fi, e.Se, s));
sort(all(M[e.Se]));
}
break;
}
if(flag == 0) {
M[e.Se].pb(pii(L + e.Fi, s));
for(int i=sz(M[e.Se])-1;i;i--) {
if(M[e.Se][i-1] > M[e.Se][i]) swap(M[e.Se][i], M[e.Se][i-1]);
else break;
}
if(sz(M[e.Se]) > 11) M[e.Se].pop_back();
pq.push(t3(L + e.Fi, e.Se, s));
}
}
}
int chk[50050] = {};
while(q--) {
int s, r; scanf("%d%d", &s, &r);
rep(a, r) {
int x; scanf("%d", &x); chk[x] = q + 10;
}
pii ans = pii(2e9, -1);
//for(pii e : M[s]) printf("%d,%d\n", e.Fi, e.Se); puts("");
for(pii e : M[s]) if(chk[e.Se] != q + 10 && ans > e) ans.Fi = e.Fi, ans.Se = e.Se;
printf("%d %d\n", ans.Se, ans.Fi);
}
}
int main(){
int tc = 1; // scanf("%d", &tc);
for(int t=1;t<=tc;t++) {
solve();
}
return 0;
};
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 4440 KB | Output is correct |
| 2 | Correct | 0 ms | 4444 KB | Output is correct |
| 3 | Correct | 0 ms | 4436 KB | Output is correct |
| 4 | Correct | 0 ms | 4440 KB | Output is correct |
| 5 | Correct | 0 ms | 4436 KB | Output is correct |
| 6 | Correct | 0 ms | 4436 KB | Output is correct |
| 7 | Correct | 0 ms | 4572 KB | Output is correct |
| 8 | Correct | 3 ms | 4572 KB | Output is correct |
| 9 | Correct | 69 ms | 9524 KB | Output is correct |
| 10 | Correct | 9 ms | 5188 KB | Output is correct |
| 11 | Correct | 29 ms | 5516 KB | Output is correct |
| 12 | Correct | 19 ms | 5496 KB | Output is correct |
| 13 | Correct | 726 ms | 44012 KB | Output is correct |
| 14 | Correct | 836 ms | 44012 KB | Output is correct |
| 15 | Correct | 109 ms | 8004 KB | Output is correct |
| 16 | Correct | 116 ms | 7608 KB | Output is correct |
| 17 | Correct | 513 ms | 14776 KB | Output is correct |
| 18 | Correct | 366 ms | 13812 KB | Output is correct |
| 19 | Correct | 523 ms | 15296 KB | Output is correct |
| 20 | Correct | 436 ms | 13948 KB | Output is correct |
| 21 | Correct | 603 ms | 15380 KB | Output is correct |
| 22 | Correct | 499 ms | 13956 KB | Output is correct |
| 23 | Correct | 699 ms | 17384 KB | Output is correct |
| 24 | Correct | 626 ms | 15688 KB | Output is correct |
| 25 | Correct | 713 ms | 17384 KB | Output is correct |
| 26 | Correct | 623 ms | 15824 KB | Output is correct |
| 27 | Correct | 103 ms | 8368 KB | Output is correct |
| 28 | Correct | 96 ms | 7928 KB | Output is correct |
| 29 | Correct | 666 ms | 16016 KB | Output is correct |
| 30 | Correct | 539 ms | 14848 KB | Output is correct |
| 31 | Correct | 686 ms | 17048 KB | Output is correct |
| 32 | Correct | 613 ms | 14584 KB | Output is correct |
| 33 | Correct | 716 ms | 17016 KB | Output is correct |
| 34 | Correct | 1008 ms | 21868 KB | Output is correct |
| 35 | Correct | 933 ms | 21544 KB | Output is correct |
| 36 | Correct | 929 ms | 22172 KB | Output is correct |
| 37 | Correct | 1126 ms | 21432 KB | Output is correct |
| 38 | Correct | 1153 ms | 22088 KB | Output is correct |
| 39 | Correct | 156 ms | 8792 KB | Output is correct |
| 40 | Correct | 139 ms | 8796 KB | Output is correct |
| 41 | Correct | 766 ms | 17944 KB | Output is correct |
| 42 | Correct | 739 ms | 17948 KB | Output is correct |
| 43 | Correct | 1163 ms | 21064 KB | Output is correct |
| 44 | Correct | 1183 ms | 21600 KB | Output is correct |
| 45 | Correct | 996 ms | 20808 KB | Output is correct |
| 46 | Correct | 1163 ms | 21464 KB | Output is correct |
| 47 | Correct | 1293 ms | 32604 KB | Output is correct |
| 48 | Correct | 1153 ms | 33116 KB | Output is correct |
| 49 | Correct | 896 ms | 32736 KB | Output is correct |
| 50 | Correct | 1033 ms | 33116 KB | Output is correct |
| 51 | Correct | 963 ms | 32996 KB | Output is correct |
| 52 | Correct | 876 ms | 33244 KB | Output is correct |
| 53 | Correct | 259 ms | 13016 KB | Output is correct |
| 54 | Correct | 1043 ms | 17220 KB | Output is correct |
| 55 | Correct | 1008 ms | 21088 KB | Output is correct |
| 56 | Correct | 956 ms | 20924 KB | Output is correct |
| 57 | Correct | 299 ms | 15868 KB | Output is correct |