CSES - IZhO 2018, day 1

Submission details
Task:	Evacuation plan
Sender:	Yytsi
Submission time:	2019-02-15 16:00:38 +0200
Language:	C++
Status:	READY
Result:	41

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	TIME LIMIT EXCEEDED	0
#3	ACCEPTED	12
#4	ACCEPTED	19
#5	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	3, 5	details
#2	ACCEPTED	0.02 s	1, 2, 3, 5	details
#3	ACCEPTED	0.01 s	1, 2, 5	details
#4	ACCEPTED	0.03 s	1, 2, 5	details
#5	ACCEPTED	0.01 s	1, 2, 3, 5	details
#6	ACCEPTED	0.02 s	1, 2, 5	details
#7	ACCEPTED	0.03 s	1, 2, 5	details
#8	ACCEPTED	0.03 s	1, 2, 5	details
#9	ACCEPTED	0.03 s	1, 2, 5	details
#10	ACCEPTED	0.04 s	1, 2, 5	details
#11	ACCEPTED	0.02 s	1, 2, 5	details
#12	ACCEPTED	0.02 s	1, 2, 5	details
#13	ACCEPTED	0.03 s	1, 2, 5	details
#14	ACCEPTED	0.03 s	1, 2, 5	details
#15	ACCEPTED	0.01 s	1, 2, 5	details
#16	ACCEPTED	0.01 s	1, 2, 5	details
#17	TIME LIMIT EXCEEDED	--	2, 5	details
#18	TIME LIMIT EXCEEDED	--	2, 5	details
#19	TIME LIMIT EXCEEDED	--	2, 5	details
#20	TIME LIMIT EXCEEDED	--	2, 5	details
#21	TIME LIMIT EXCEEDED	--	2, 5	details
#22	TIME LIMIT EXCEEDED	--	2, 5	details
#23	TIME LIMIT EXCEEDED	--	2, 5	details
#24	TIME LIMIT EXCEEDED	--	2, 5	details
#25	TIME LIMIT EXCEEDED	--	2, 5	details
#26	TIME LIMIT EXCEEDED	--	2, 5	details
#27	TIME LIMIT EXCEEDED	--	2, 5	details
#28	TIME LIMIT EXCEEDED	--	2, 5	details
#29	TIME LIMIT EXCEEDED	--	2, 5	details
#30	TIME LIMIT EXCEEDED	--	2, 5	details
#31	TIME LIMIT EXCEEDED	--	2, 5	details
#32	ACCEPTED	0.02 s	3, 5	details
#33	ACCEPTED	0.03 s	3, 5	details
#34	ACCEPTED	0.03 s	3, 5	details
#35	ACCEPTED	0.03 s	3, 5	details
#36	ACCEPTED	0.02 s	3, 5	details
#37	ACCEPTED	0.03 s	3, 5	details
#38	ACCEPTED	0.02 s	3, 5	details
#39	ACCEPTED	0.02 s	3, 5	details
#40	ACCEPTED	0.03 s	3, 5	details
#41	ACCEPTED	0.02 s	3, 5	details
#42	ACCEPTED	0.32 s	4, 5	details
#43	ACCEPTED	0.51 s	4, 5	details
#44	ACCEPTED	0.53 s	4, 5	details
#45	ACCEPTED	0.17 s	4, 5	details
#46	ACCEPTED	0.70 s	4, 5	details
#47	ACCEPTED	0.51 s	4, 5	details
#48	ACCEPTED	0.50 s	4, 5	details
#49	ACCEPTED	0.45 s	4, 5	details
#50	ACCEPTED	0.49 s	4, 5	details
#51	ACCEPTED	0.56 s	4, 5	details
#52	ACCEPTED	0.55 s	4, 5	details
#53	ACCEPTED	0.54 s	4, 5	details
#54	ACCEPTED	0.56 s	4, 5	details
#55	ACCEPTED	0.47 s	4, 5	details
#56	ACCEPTED	0.54 s	4, 5	details
#57	ACCEPTED	0.54 s	4, 5	details
#58	ACCEPTED	0.48 s	4, 5	details
#59	ACCEPTED	0.47 s	4, 5	details
#60	ACCEPTED	0.09 s	2, 4, 5	details
#61	ACCEPTED	0.60 s	4, 5	details
#62	ACCEPTED	0.40 s	4, 5	details
#63	ACCEPTED	0.14 s	4, 5	details
#64	ACCEPTED	0.22 s	4, 5	details
#65	ACCEPTED	0.12 s	4, 5	details
#66	ACCEPTED	0.12 s	4, 5	details
#67	ACCEPTED	0.12 s	4, 5	details
#68	ACCEPTED	0.17 s	4, 5	details
#69	ACCEPTED	0.11 s	4, 5	details
#70	ACCEPTED	0.18 s	4, 5	details
#71	ACCEPTED	0.11 s	4, 5	details
#72	ACCEPTED	0.17 s	4, 5	details
#73	TIME LIMIT EXCEEDED	--	5	details
#74	TIME LIMIT EXCEEDED	--	5	details
#75	TIME LIMIT EXCEEDED	--	5	details
#76	TIME LIMIT EXCEEDED	--	5	details
#77	TIME LIMIT EXCEEDED	--	5	details
#78	TIME LIMIT EXCEEDED	--	5	details
#79	TIME LIMIT EXCEEDED	--	5	details
#80	TIME LIMIT EXCEEDED	--	5	details
#81	TIME LIMIT EXCEEDED	--	5	details
#82	TIME LIMIT EXCEEDED	--	5	details
#83	TIME LIMIT EXCEEDED	--	5	details
#84	TIME LIMIT EXCEEDED	--	5	details
#85	TIME LIMIT EXCEEDED	--	5	details
#86	TIME LIMIT EXCEEDED	--	5	details
#87	TIME LIMIT EXCEEDED	--	5	details
#88	TIME LIMIT EXCEEDED	--	5	details
#89	TIME LIMIT EXCEEDED	--	5	details
#90	TIME LIMIT EXCEEDED	--	5	details
#91	TIME LIMIT EXCEEDED	--	5	details
#92	TIME LIMIT EXCEEDED	--	5	details
#93	TIME LIMIT EXCEEDED	--	5	details
#94	TIME LIMIT EXCEEDED	--	5	details
#95	TIME LIMIT EXCEEDED	--	5	details
#96	TIME LIMIT EXCEEDED	--	5	details
#97	TIME LIMIT EXCEEDED	--	5	details
#98	TIME LIMIT EXCEEDED	--	5	details
#99	TIME LIMIT EXCEEDED	--	5	details
#100	TIME LIMIT EXCEEDED	--	5	details
#101	TIME LIMIT EXCEEDED	--	5	details

Code

// No chance in hell


#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 101010
int n, m, k;
vector<pll> adj[N];
ll d[N]; // shortest dist to a npp
int vis[N];
int id = 1;
bool npp[N];
bool calc[N];
ll res[N];
vector<pii> query[N];
ll answer[N];

bool ok(int a, int b, ll min_w) {
  id++;
  queue<int> q;
  q.push(a);
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for (pll u : adj[x]) {
      if (vis[u.F] == id || d[u.F] < min_w) continue;
      vis[u.F] = id;
      q.push(u.F);
    }
  }

  if (vis[b] == id) return true;
  else return false;
}

ll dijkstra(int x) {
  FOR(i,1,n+1) d[i] = 1e15;
  d[x] = 0;
  priority_queue<pll, vector<pll>, greater<pll>> q;
  q.push({0, x});
  ll mn = 1e15;
 
  id++;
  while (!q.empty()) {
    int x = q.top().S; q.pop();
    if (vis[x] == id) continue;
    vis[x] = id;
    for (pll u : adj[x]) {
      if (calc[u.F]) {
        mn = min(mn, res[u.F]);
      }
      if (d[x] + u.S < d[u.F]) {
        d[u.F] = d[x] + u.S;
        if (npp[u.F]) mn = min(mn, d[u.F]);
        q.push({d[u.F], u.F});
      }
    }
  }
 
  return mn;
}

ll tirsk(int x) {
  if (calc[x]) return res[x];
  res[x] = dijkstra(x);
  calc[x] = true;
  return res[x];
}

int main() {
  IO; cin>>n>>m;
  FOR(i,0,m) {
    int a,b; ll w;
    cin>>a>>b>>w;
    adj[a].pb({b, w});
    adj[b].pb({a, w});
  }

  FOR(i,1,n+1) d[i] = 1e15;
  priority_queue<pll, vector<pll>, greater<pll>> q;

  cin>>k;
  FOR(i,0,k) {
    int x; cin>>x;
    d[x] = 0;
    npp[x] = true;
    q.push({0, x});
  }

  int Q; cin>>Q;
  if (Q == 1) goto skip;
  if ((Q > 1000) || (n > 1000)) {
    FOR(i,0,Q) {
      int a,b; cin>>a>>b;
      query[a].pb({b, i});
    }

    FOR(a,1,n+1) {
      if (!query[a].size()) continue;
      for (pii s : query[a]) {
        int i = s.S;
        int b = s.F;
        answer[i]=min(tirsk(a), tirsk(b));
      }
    }
    
    FOR(i,0,Q) cout<<answer[i]<<"\n";
    return 0;
  }

  skip:
  while (!q.empty()) {
    int x = q.top().S; q.pop();
    if (vis[x] == id) continue;
    vis[x] = id;
    for (pll u : adj[x]) {
      if (d[x] + u.S < d[u.F]) {
        d[u.F] = d[x] + u.S;
        q.push({d[u.F], u.F});
      }
    }
  }

  FOR(i,0,Q) {
    int a,b; cin>>a>>b;
    if (!d[a] || !d[b]) {
      cout<<0<<"\n";
      continue;
    }
    // binary search max dist to npp on path a->b?
    bool friends = false;
    for (pll u : adj[a]) if (u.F == b) friends = true;

    if (friends) {
      cout<<min(d[a], d[b])<<"\n"; continue;
    }
    ll ck = 0;
    for (ll z = min(d[a], d[b]); z >= 1; z /= 2) {
      while (ok(a, b, ck+z) && ok(b, a, ck+z)) ck += z;
    }

    cout<<ck<<"\n";
  }
}

Test details

Test 1

Group: 3, 5

Verdict: ACCEPTED

input
`9 12 1 9 4 1 2 5 2 3 7 2 4 3 ...` view save

correct output
`5 5 0 7 8` view save

user output
`5 5 0 7 8` view save

Test 2

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`10 20 1 2 657 1 3 522 1 4 448 3 5 855 ...` view save

correct output
`0 408 541 541 432 ...` view save

user output
`0 408 541 541 432 ...` view save

Test 3

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 999 588 473 61 588 91 30 588 75 125 588 980 551 ...` view save

correct output
`552 552 552 552 552 ...` view save

user output
`552 552 552 552 552 ...` Truncated

Test 4

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 999 975 859 302 975 422 394 975 634 444 975 439 384 ...` view save

correct output
`37 37 37 37 37 ...` view save

user output
`37 37 37 37 37 ...` Truncated

Test 5

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
`10 9 7 3 759 7 2 864 7 5 89 7 10 855 ...` view save

correct output
`491 491 491 0 491 ...` view save

user output
`491 491 491 0 491 ...` view save

Test 6

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 999 585 395 355 585 651 77 585 728 215 585 392 955 ...` view save

correct output
`6 6 6 6 6 ...` view save

user output
`6 6 6 6 6 ...` Truncated

Test 7

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 999 986 358 7 986 142 732 986 586 346 986 193 901 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 8

Group: 1, 2, 5

Verdict: ACCEPTED

input
`100 200 1 2 828 1 3 496 1 4 331 2 5 347 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` view save

Test 9

Group: 1, 2, 5

Verdict: ACCEPTED

input
`100 200 1 2 333 2 3 309 3 4 901 1 5 429 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` view save

Test 10

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 1000 1 2 980 2 3 726 3 4 888 4 5 810 ...` view save

correct output
`2768 3408 4109 5400 2412 ...` view save

user output
`2768 3408 4109 5400 2412 ...` Truncated

Test 11

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 1000 1 2 353 1 3 672 3 4 861 4 5 517 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 12

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 1000 1 2 127 2 3 854 1 4 813 4 5 8 ...` view save

correct output
`3925 2711 2047 2304 1751 ...` view save

user output
`3925 2711 2047 2304 1751 ...` Truncated

Test 13

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 999 340 299 654 340 911 553 340 232 256 340 761 558 ...` view save

correct output
`226 226 226 226 226 ...` view save

user output
`226 226 226 226 226 ...` Truncated

Test 14

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 1000 1 2 188 2 3 247 3 4 641 2 5 473 ...` view save

correct output
`638 863 441 0 976 ...` view save

user output
`638 863 441 0 976 ...` Truncated

Test 15

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 1000 1 2 393 2 3 682 2 4 841 1 5 84 ...` view save

correct output
`5609 6225 5028 3588 4348 ...` view save

user output
`5609 6225 5028 3588 4348 ...` Truncated

Test 16

Group: 1, 2, 5

Verdict: ACCEPTED

input
`1000 1000 1 2 569 1 3 813 2 4 461 4 5 493 ...` view save

correct output
`5350 2221 1313 3010 3983 ...` view save

user output
`5350 2221 1313 3010 3983 ...` Truncated

Test 17

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`77777 99999 1 2 891 2 3 879 3 4 604 4 5 254 ...` view save

correct output
`4493 3124 3584 4203 3352 ...` view save

user output
(empty)

Test 18

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 13 1 3 882 3 4 392 2 5 498 ...` view save

correct output
`852 901 1120 1165 1239 ...` view save

user output
(empty)

Test 19

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`12321 41332 1 2 81 2 3 165 3 4 941 2 5 167 ...` view save

correct output
`1270 1486 1185 1113 1222 ...` view save

user output
(empty)

Test 20

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 38940 18613 406 38940 77994 688 38940 1918 847 38940 33444 215 ...` view save

correct output
`104 104 104 104 104 ...` view save

user output
(empty)

Test 21

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 461 2 3 439 2 4 578 3 5 317 ...` view save

correct output
`1097 717 1251 955 1045 ...` view save

user output
(empty)

Test 22

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 200000 1 2 984 1 3 96 1 4 469 3 5 480 ...` view save

correct output
`323 0 156 79 0 ...` view save

user output
(empty)

Test 23

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 86937 75997 956 75997 86103 901 86103 13024 918 13024 85212 947 ...` view save

correct output
`29396767 21591510 55276964 33539480 72080903 ...` view save

user output
(empty)

Test 24

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 761 1 3 820 3 4 219 4 5 989 ...` view save

correct output
`970 711 780 699 716 ...` view save

user output
(empty)

Test 25

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 697 2 3 846 1 4 365 4 5 576 ...` view save

correct output
`355 625 766 605 583 ...` view save

user output
(empty)

Test 26

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 295 2 3 254 2 4 820 1 5 418 ...` view save

correct output
`55 371 0 341 0 ...` view save

user output
(empty)

Test 27

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 60099 24766 247 60099 62884 191 60099 59379 971 60099 30532 420 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
(empty)

Test 28

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 49317 55052 770 49317 54295 838 49317 44228 765 49317 97326 531 ...` view save

correct output
`35 35 35 35 35 ...` view save

user output
(empty)

Test 29

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 12914 47476 547 12914 96120 727 12914 44181 338 12914 36309 794 ...` view save

correct output
`6 6 6 6 6 ...` view save

user output
(empty)

Test 30

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 49333 95815 271 49333 26107 718 49333 43319 270 49333 41236 458 ...` view save

correct output
`62 62 62 62 62 ...` view save

user output
(empty)

Test 31

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 35081 4986 303 35081 4729 336 35081 7666 670 35081 28578 508 ...` view save

correct output
`257 257 257 257 257 ...` view save

user output
(empty)

Test 32

Group: 3, 5

Verdict: ACCEPTED

input
`15 20 1 2 429 2 3 101 3 4 174 4 5 733 ...` view save

correct output
`226 416 325 325 416 ...` view save

user output
`226 416 325 325 416 ...` Truncated

Test 33

Group: 3, 5

Verdict: ACCEPTED

input
`15 25 1 2 906 2 3 853 1 4 546 3 5 623 ...` view save

correct output
`295 295 0 0 794 ...` view save

user output
`295 295 0 0 794 ...` Truncated

Test 34

Group: 3, 5

Verdict: ACCEPTED

input
`15 40 1 2 406 2 3 911 1 4 725 2 5 482 ...` view save

correct output
`190 406 0 0 190 ...` view save

user output
`190 406 0 0 190 ...` Truncated

Test 35

Group: 3, 5

Verdict: ACCEPTED

input
`15 70 1 2 732 2 3 729 3 4 174 1 5 417 ...` view save

correct output
`61 108 149 61 0 ...` view save

user output
`61 108 149 61 0 ...` Truncated

Test 36

Group: 3, 5

Verdict: ACCEPTED

input
`15 100 1 2 186 1 3 309 3 4 38 3 5 229 ...` view save

correct output
`38 49 0 0 0 ...` view save

user output
`38 49 0 0 0 ...` Truncated

Test 37

Group: 3, 5

Verdict: ACCEPTED

input
`15 100 1 2 46 1 3 998 1 4 524 1 5 42 ...` view save

correct output
`0 0 66 68 78 ...` view save

user output
`0 0 66 68 78 ...` Truncated

Test 38

Group: 3, 5

Verdict: ACCEPTED

input
`15 89 1 2 590 1 3 542 2 4 430 3 5 13 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 39

Group: 3, 5

Verdict: ACCEPTED

input
`15 14 1 2 738 1 3 739 3 4 465 1 5 134 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 40

Group: 3, 5

Verdict: ACCEPTED

input
`15 14 15 8 438 15 11 672 15 12 20 15 7 752 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 41

Group: 3, 5

Verdict: ACCEPTED

input
`15 100 1 2 451 1 3 701 1 4 637 1 5 547 ...` view save

correct output
`164 158 0 152 117 ...` view save

user output
`164 158 0 152 117 ...` Truncated

Test 42

Group: 4, 5

Verdict: ACCEPTED

input
`100000 200000 1 2 931 2 3 916 1 4 342 2 5 18 ...` view save

correct output
`2782` view save

user output
`2782` view save

Test 43

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 485 1 3 567 2 4 479 1 5 166 ...` view save

correct output
`1480` view save

user output
`1480` view save

Test 44

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 129 2 3 866 1 4 165 1 5 254 ...` view save

correct output
`1084` view save

user output
`1084` view save

Test 45

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 55393 66829 903 66829 72184 985 72184 47162 950 47162 22279 989 ...` view save

correct output
`0` view save

user output
`0` view save

Test 46

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 783 2 3 877 2 4 834 1 5 734 ...` view save

correct output
`557` view save

user output
`557` view save

Test 47

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 817 1 3 411 1 4 947 2 5 943 ...` view save

correct output
`794` view save

user output
`794` view save

Test 48

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 212 1 3 723 1 4 614 4 5 819 ...` view save

correct output
`712` view save

user output
`712` view save

Test 49

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 203 2 3 684 2 4 766 3 5 287 ...` view save

correct output
`879` view save

user output
`879` view save

Test 50

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 879 2 3 322 3 4 851 3 5 348 ...` view save

correct output
`950` view save

user output
`950` view save

Test 51

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 36 1 3 883 2 4 519 3 5 579 ...` view save

correct output
`837` view save

user output
`837` view save

Test 52

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 1000 1 3 207 1 4 668 4 5 272 ...` view save

correct output
`499` view save

user output
`499` view save

Test 53

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 991 1 3 104 1 4 717 4 5 165 ...` view save

correct output
`447` view save

user output
`447` view save

Test 54

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 803 1 3 429 3 4 634 4 5 99 ...` view save

correct output
`315` view save

user output
`315` view save

Test 55

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 33 1 3 661 1 4 630 3 5 685 ...` view save

correct output
`350` view save

user output
`350` view save

Test 56

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 636 2 3 716 1 4 58 2 5 337 ...` view save

correct output
`50` view save

user output
`50` view save

Test 57

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 294 2 3 768 1 4 524 1 5 307 ...` view save

correct output
`366` view save

user output
`366` view save

Test 58

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 87 1 3 998 3 4 888 4 5 103 ...` view save

correct output
`759` view save

user output
`759` view save

Test 59

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 176 2 3 314 3 4 513 2 5 686 ...` view save

correct output
`1222` view save

user output
`1222` view save

Test 60

Group: 2, 4, 5

Verdict: ACCEPTED

input
`100000 99999 62990 65315 931 65315 3455 970 3455 98310 995 98310 23065 952 ...` view save

correct output
`95052504` view save

user output
`95052504` view save

Test 61

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 585 2 3 805 3 4 581 1 5 572 ...` view save

correct output
`800` view save

user output
`800` view save

Test 62

Group: 4, 5

Verdict: ACCEPTED

input
`100000 500000 1 2 150 1 3 624 3 4 361 1 5 742 ...` view save

correct output
`0` view save

user output
`0` view save

Test 63

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 42321 26741 992 42321 69329 304 42321 5758 819 42321 29266 648 ...` view save

correct output
`111` view save

user output
`111` view save

Test 64

Group: 4, 5

Verdict: ACCEPTED

input
`100000 100000 51519 55325 253 55325 18282 583 18282 90551 470 90551 91972 266 ...` view save

correct output
`1057897` view save

user output
`1057897` view save

Test 65

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 54801 39194 733 54801 39401 162 54801 65113 479 54801 61590 30 ...` view save

correct output
`3` view save

user output
`3` view save

Test 66

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 15780 41412 52 15780 99212 342 15780 8094 961 15780 33547 16 ...` view save

correct output
`19` view save

user output
`19` view save

Test 67

Group: 4, 5

Verdict: ACCEPTED

input
`100000 100000 76627 21712 427 21712 26993 256 26993 80393 100 80393 56194 44 ...` view save

correct output
`0` view save

user output
`0` view save

Test 68

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 88549 9364 973 9364 6403 998 6403 29693 969 29693 59321 938 ...` view save

correct output
`0` view save

user output
`0` view save

Test 69

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 60084 18317 681 60084 77472 797 60084 93299 190 60084 76120 745 ...` view save

correct output
`1` view save

user output
`1` view save

Test 70

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 67813 44109 993 44109 32579 980 32579 83236 911 83236 58703 958 ...` view save

correct output
`0` view save

user output
`0` view save

Test 71

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 99416 74269 87 99416 87958 424 99416 43397 39 99416 62377 783 ...` view save

correct output
`1` view save

user output
`1` view save

Test 72

Group: 4, 5

Verdict: ACCEPTED

input
`100000 99999 80340 75986 985 75986 12073 987 12073 14775 998 14775 51604 912 ...` view save

correct output
`0` view save

user output
`0` view save

Test 73

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 200000 1 2 641 2 3 327 2 4 612 3 5 929 ...` view save

correct output
`2789 2693 2317 2490 2585 ...` view save

user output
(empty)

Test 74

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 423 1 3 258 3 4 573 2 5 503 ...` view save

correct output
`943 879 757 840 810 ...` view save

user output
(empty)

Test 75

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 696 2 3 91 1 4 594 1 5 389 ...` view save

correct output
`928 915 909 978 302 ...` view save

user output
(empty)

Test 76

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 839 1 3 344 1 4 742 3 5 969 ...` view save

correct output
`741 1036 993 553 1057 ...` view save

user output
(empty)

Test 77

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 451 1 3 46 3 4 291 4 5 937 ...` view save

correct output
`876 692 608 407 459 ...` view save

user output
(empty)

Test 78

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 750 1 3 891 2 4 533 1 5 421 ...` view save

correct output
`662 632 594 622 601 ...` view save

user output
(empty)

Test 79

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 300 2 3 460 3 4 834 3 5 381 ...` view save

correct output
`594 954 739 873 953 ...` view save

user output
(empty)

Test 80

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 311 1 3 228 2 4 42 3 5 981 ...` view save

correct output
`596 977 754 830 731 ...` view save

user output
(empty)

Test 81

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 655 1 3 626 1 4 92 1 5 719 ...` view save

correct output
`588 957 831 766 558 ...` view save

user output
(empty)

Test 82

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 241 2 3 717 2 4 756 4 5 555 ...` view save

correct output
`1077 655 838 981 1077 ...` view save

user output
(empty)

Test 83

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 22 2 3 950 2 4 300 2 5 192 ...` view save

correct output
`457 426 389 460 518 ...` view save

user output
(empty)

Test 84

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 235 1 3 508 3 4 611 1 5 468 ...` view save

correct output
`215 458 591 147 495 ...` view save

user output
(empty)

Test 85

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 203 1 3 412 3 4 390 2 5 433 ...` view save

correct output
`215 314 284 413 301 ...` view save

user output
(empty)

Test 86

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 427 2 3 613 1 4 102 1 5 320 ...` view save

correct output
`171 16 110 184 63 ...` view save

user output
(empty)

Test 87

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 738 2 3 891 3 4 468 4 5 717 ...` view save

correct output
`505 51 370 297 108 ...` view save

user output
(empty)

Test 88

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 552 2 3 990 1 4 264 3 5 715 ...` view save

correct output
`589 751 640 868 540 ...` view save

user output
(empty)

Test 89

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 928 2 3 476 3 4 531 4 5 166 ...` view save

correct output
`1015 996 1150 995 1045 ...` view save

user output
(empty)

Test 90

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 92489 77658 971 77658 44038 908 44038 16706 947 16706 86719 936 ...` view save

correct output
`95057187 21105802 9382625 33465301 45188238 ...` view save

user output
(empty)

Test 91

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 499 2 3 548 1 4 153 3 5 7 ...` view save

correct output
`978 983 634 768 627 ...` view save

user output
(empty)

Test 92

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 500000 1 2 663 1 3 944 1 4 67 1 5 976 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 93

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 12420 1528 466 12420 42872 479 12420 8461 723 12420 75677 717 ...` view save

correct output
`55 55 55 55 55 ...` view save

user output
(empty)

Test 94

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 100000 55076 46178 852 46178 35188 936 35188 36448 616 36448 20101 711 ...` view save

correct output
`405459 1058750 3569995 3807 2822955 ...` view save

user output
(empty)

Test 95

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 86054 48657 652 86054 68231 412 86054 29096 379 86054 59437 691 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
(empty)

Test 96

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 39950 45152 493 39950 48400 664 39950 31284 726 39950 86952 141 ...` view save

correct output
`14 14 14 14 14 ...` view save

user output
(empty)

Test 97

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 100000 12935 19528 317 19528 89291 248 89291 70689 378 70689 6165 906 ...` view save

correct output
`1087 0 0 0 159917 ...` view save

user output
(empty)

Test 98

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 40231 61273 959 61273 21887 924 21887 63910 986 63910 64968 933 ...` view save

correct output
`0 6434711 9195470 0 0 ...` view save

user output
(empty)

Test 99

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 74744 3772 134 74744 37184 823 74744 15444 783 74744 96445 78 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
(empty)

Test 100

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 50234 26601 934 26601 98648 926 98648 57972 967 57972 43476 947 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 101

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100000 99999 56054 80449 561 56054 9214 259 56054 62006 238 56054 80043 946 ...` view save

correct output
`23 23 23 23 23 ...` view save

user output
(empty)

IZhO 2018, day 1

Evacuation plan

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Test 65

Test 66

Test 67

Test 68

Test 69

Test 70

Test 71

Test 72

Test 73

Test 74

Test 75

Test 76