Submission #966965

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
966965	2024-04-20 17:56:17	Hugo1729	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	682 ms	79976 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 <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
vector<pair<int,int>> adj[100000];
int visited[100000]={0};
int dp[100000]={0};
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for(int i=0;i<K;i++)visited[P[i]]=2;
    priority_queue<pair<int,int>> pq;
    for(int i=0;i<M;i++){
        int v=R[i][0],w=R[i][1];
        if(!(visited[v]==2&&visited[w]==2)){
            if(!(visited[v]==2))swap(v,w);
            if(visited[v])pq.push({-L[i],w});
        }
        adj[R[i][0]].push_back({R[i][1],L[i]});
        adj[R[i][1]].push_back({R[i][0],L[i]});
    }
    while(!pq.empty()){
        int d = -pq.top().first, v = pq.top().second;
        // cout << "s" << v << ' ' << d << '\n';
        pq.pop();
        if(visited[v]==2)continue;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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