oj.uz

답안 #497261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497261 2021-12-22T21:47:25 Z Skywk 악어의 지하 도시 (IOI11_crocodile) C++14
100 / 100
 669 ms 84580 KB 
#include "crocodile.h"
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include<queue>
#include<stack>
#define lmt 100000
#define LMT 1000000
#define mod 1000000007
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
 
using namespace std;

vector<pil> graph[lmt];
long long best[LMT];
bool once[LMT];

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for(int i=0; i<m;  i++)
    {
        int a=R[i][0], b=R[i][1];
        graph[a].push_back({b, L[i]});
        graph[b].push_back({a, L[i]});
    }
    
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for(int i=0, x; i<k; i++)
        pq.push({0, P[i]});

    for(int i=0; i<n; i++)
        best[i]=-1;
    while(!pq.empty())
    {
        auto p=pq.top();
        pq.pop();
        int x=p.second; long long w=p.first;

        if(best[x] != -1)
            continue;
        if(w!=0 && !once[x])
        {
            once[x]=true;
            continue;
        }

        best[x]=w;
        for(auto y : graph[x])
        {
            if(best[y.first] != -1)
                continue;
            pq.push({w+y.second, y.first});
        }
    }
    return best[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:37:18: warning: unused variable 'x' [-Wunused-variable]
   37 |     for(int i=0, x; i<k; i++)
      |                  ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2604 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2756 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 1 ms 2764 KB Output is correct
9 Correct 3 ms 3220 KB Output is correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 5 ms 3660 KB Output is correct
13 Correct 5 ms 3788 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2604 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2756 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 1 ms 2764 KB Output is correct
9 Correct 3 ms 3220 KB Output is correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 5 ms 3660 KB Output is correct
13 Correct 5 ms 3788 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 632 ms 80992 KB Output is correct
17 Correct 71 ms 13772 KB Output is correct
18 Correct 90 ms 16056 KB Output is correct
19 Correct 669 ms 84580 KB Output is correct
20 Correct 418 ms 71640 KB Output is correct
21 Correct 51 ms 8156 KB Output is correct
22 Correct 378 ms 50300 KB Output is correct