제출 #279874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
279874		shinjan	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	2 ms	2688 KiB

crocodile

#include <iostream>
#include <bits/stdc++.h>
#define maxN 100001
#define maxM 1000001
#include "crocodile.h"
using namespace std;
vector<pair<int,int>> drvo[maxN];
bitset <maxN> spec;
int mini[maxN];
int siguran[maxN];
void namesti(int n)
{
    for(int i=0;i<n;i++)
    {
        siguran[i]=-1;
        mini[i]=-1;
    }
}
void dfs(int v,int par)
{
    int cvor,w;
    for(pair<int,int> p:drvo[v])
    {
        cvor=p.first;
        w=p.second;
        if(cvor!=par)
        {
            if(spec[cvor])
            {
                if(mini[v]>w || mini[v]==-1)
                {
                    siguran[v]=mini[v];
                    mini[v]=w;
                }
                else if(w<siguran[v] || siguran[v]==-1)
                {
                    siguran[v]=w;
                }
            }
            else{
                dfs(cvor,v);
                if(siguran[cvor]+w<mini[v] || mini[v]==-1)
                {
                    siguran[v]=mini[v];
                    mini[v]=siguran[cvor]+w;
                }
                else if(siguran[cvor]+w<siguran[v] || siguran[v]==-1)
                {
                    siguran[v]=siguran[cvor]+w;
                }
            }
        }
    }
}
int travel_plan(int n,int m,int r[maxM][2],int l[maxM],int k,int p[maxN])
{
    for(int i=0;i<m;i++)
    {
        drvo[r[i][0]].push_back({r[i][1],l[i]});
        drvo[r[i][1]].push_back({r[i][0],l[i]});
    }
    for(int i=0;i<k;i++)
    {
        spec[p[i]]=1;
    }
    dfs(0,-1);
    return siguran[0];
}

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