oj.uz

Submission #154843

# Submission time Handle Problem Language Result Execution time Memory
154843 2019-09-25T08:46:31 Z davitmarg Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 265 ms 262148 KB 
/*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



*/

Compilation message

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2812 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2812 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2812 KB Output is correct
8 Correct 5 ms 2940 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -