oj.uz

답안 #1069041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069041 2024-08-21T15:07:46 Z DeathIsAwe 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 678 ms 82196 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
bool visited[100000];
pair<int,int> dist[100000];


class compare {
  public: bool operator()(vector<int> a, vector<int> b) {
    if (a[0] == b[0]) {
      if (a[1] == b[1]) {
        return a[2] > b[2];
      }
      return a[1] > b[1];
    }
    return a[0] > b[0];
  }
};


int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
  vector<vector<pair<int,int>>> graph(100000);
  for (int i=0;i<m;i++) {
    graph[r[i][0]].push_back(make_pair(r[i][1], l[i]));
    graph[r[i][1]].push_back(make_pair(r[i][0], l[i]));
  }
  for (int i=0;i<100000;i++) {
    visited[i] = false;
    dist[i].first = INT_MAX;
    dist[i].second = INT_MAX;
  }


  priority_queue<vector<int>, vector<vector<int>>, compare> pq;
  vector<int> dum(3), top(3);
  for (int i=0;i<k;i++) {
    dum[0] = 0; dum[1] = 0; dum[2] = p[i];
    pq.push(dum);
    dist[p[i]].first = 0; dist[p[i]].second = 0;
  }
  

  int bruh;
  while (pq.size() > 0) {
    top = pq.top(); pq.pop();
    //cout << top[0] << ' ' << top[1] << ' ' << top[2] << '\n';
    if (visited[top[2]]) {continue;}
    visited[top[2]] = true;
    for (pair<int,int> i: graph[top[2]]) {
      if (!visited[i.first]) {
        bruh = i.second + top[0];
        if (bruh < dist[i.first].second) {
          dist[i.first].first = dist[i.first].second;
          dist[i.first].second = bruh;
          dum[0] = dist[i.first].first; dum[1] = dist[i.first].second; dum[2] = i.first;
          pq.push(dum);
        } else  if (bruh < dist[i.first].first) {
          dist[i.first].first = bruh;
          dum[0] = dist[i.first].first; dum[1] = dist[i.first].second; dum[2] = i.first;
          pq.push(dum);
        }
      }
    }
  }


  //for (int i=0;i<n;i++) {
  //  cout << dist[i].first << ' ' << dist[i].second << '\n';
  //}
  return dist[0].first;
}

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 3 ms 7120 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 3 ms 7132 KB Output is correct
12 Correct 4 ms 7512 KB Output is correct
13 Correct 3 ms 7512 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 3 ms 7120 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 3 ms 7132 KB Output is correct
12 Correct 4 ms 7512 KB Output is correct
13 Correct 3 ms 7512 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct
16 Correct 399 ms 68240 KB Output is correct
17 Correct 191 ms 22484 KB Output is correct
18 Correct 210 ms 23556 KB Output is correct
19 Correct 678 ms 82196 KB Output is correct
20 Correct 163 ms 54608 KB Output is correct
21 Correct 68 ms 12300 KB Output is correct
22 Correct 284 ms 51556 KB Output is correct