제출 #154843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154843		davitmarg	악어의 지하 도시 (IOI11_crocodile)	C++17	46 / 100	265 ms	262148 KiB

crocodile

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;

// #ifndef death
//     #include "grader.h"
// #endif

int n,m,k,win[100005];
LL dp[100005];
vector<pair<int,LL>> g[100005];

void dfs(int v,int p)
{
    if(win[v]==1)
    {
        dp[v]=0;
        return;
    }
    vector<LL> t;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i].first;
        LL d=g[v][i].second;
        if(to==p)
            continue;
        dfs(to,v);
        if(win[to]==1)
            t.PB(dp[to]+d);
    }
    if(t.size()<=1)
        return;
    sort(all(t));
    win[v]=1;
    dp[v]=t[1];
}

LL travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
    n=N;
    m=M;
    k=K;
    for(int i=0;i<m;i++)
    {
        int a,b;
        LL d;
        a=R[i][0]+1;
        b=R[i][1]+1;
        d=L[i];
        g[a].PB(MP(b,d));
        g[b].PB(MP(a,d));
    }
    for(int i=0;i<k;i++)
        win[P[i]+1]=1;
    dfs(1,0);
    return dp[1];
}

#ifdef death

int main()
{
    int N,M,K,R[102][2],P[102];
    int L[102];
    cin>>N>>M>>K;
    for(int i=0;i<M;i++)
        cin>>R[i][0]>>R[i][1]>>L[i];
    for(int i=0;i<K;i++)
        cin>>P[i];
    cout<<travel_plan(N,M,R,L,K,P);
	return 0;
}

#endif
 
/*

2
4 5
1 2



*/

컴파일 시 표준 에러 (stderr) 메시지

crocodile.cpp: In function 'void dfs(int, int)':
crocodile.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~

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