Submission #234891

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
234891	2020-05-26 07:09:52	Nodir_Bobiev	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	731 ms	45904 KiB

crocodile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector < pair < int, int > > gr[111111];
int cnt[111111], min1[111111], min2[111111], Vmin1[111111], Vmin2[111111];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int i = 0; i < M; i ++ ){
    gr[R[i][0]].push_back({L[i], R[i][1]});
    gr[R[i][1]].push_back({L[i], R[i][0]});
  }
  for( int i = 0; i < N; i ++ ){
    min1[i] = min2[i] = 1e9+10;
  }
  queue < pair < int, int > > q;
  for( int i = 0; i < K; i ++ ){
    min1[P[i]] = min2[P[i]] = 0;
    q.push({0, P[i]});
  }
  while(!q.empty()){
    pair < int, int > pp = q.front(); q.pop();
    int c = pp.first, v = pp.second;
    if( cnt[v] != c ) continue;
    for( auto edge: gr[v] ){
      int cost = edge.first, to = edge.second;
      if( min1[to] > min2[v]+cost ){
        if( Vmin1[to] == v ){
          min1[to] = min2[v]+cost;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 0 / 11