oj.uz

답안 #279905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
279905 2020-08-22T11:59:07 Z shinjan 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 2 ms 2688 KB 
#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]!=-1 && (siguran[cvor]+w<=mini[v] || mini[v]==-1))
                {
                    siguran[v]=mini[v];
                    mini[v]=siguran[cvor]+w;
                }
                else if(siguran[cvor]!=-1 && (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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -