oj.uz

Submission #154844

# Submission time Handle Problem Language Result Execution time Memory
154844 2019-09-25T09:29:13 Z davitmarg Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1576 ms 101924 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],p[100005],used[100005];
vector<pair<int,LL>> g[100005];
pair<LL,LL> dp[100005];

void add(pair<LL,LL> &p,LL val)
{
    if(val<=p.first)
    {
        p.second=p.first;
        p.first=val;
    }
    else if(p.second>val)
        p.second=val;
}

int 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<k;i++)
    {
        p[i+1]=P[i]+1;
        win[P[i]+1]=1;
    }
    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];

        if(win[a] && win[b])
            continue;

        g[a].PB(MP(b,d));
        g[b].PB(MP(a,d));
    }

    for(int i=1;i<=n;i++)
        dp[i]=MP(mod*mod,mod*mod);

    priority_queue<pair<LL,int>> q;
    for(int i=1;i<=k;i++)
    {
        q.push(MP(0,p[i]));
        dp[p[i]]=MP(0,0);
    }
    while(!q.empty())
    {
        int v=-1;
        do
        {
            v=q.top().second;
            q.pop();
        } while (used[v] && !q.empty());

        if(used[v] || v==-1)
            break;
        used[v]=1;
        //cout<<v<<" = "<<dp[v].second<<endl;
        for(int i=0;i<g[v].size();i++)
        {
            int to=g[v][i].first;
            LL d=g[v][i].second;
            add(dp[to],dp[v].second+d);
            q.push( MP(-dp[to].second,to) );
        }   
    }
    //cout<<dp[1].first<<" : "<<dp[1].second<<endl;
    return dp[1].second;
}

#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 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:92:22: 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 2808 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 2852 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct

Subtask #2
43.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 2808 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 2852 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 8 ms 3152 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 6 ms 2936 KB Output is correct
12 Correct 12 ms 3576 KB Output is correct
13 Correct 12 ms 3704 KB Output is correct
14 Correct 5 ms 2808 KB Output is correct
15 Correct 6 ms 2936 KB Output is correct

Subtask #3
11.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 2808 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 2852 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 8 ms 3152 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 6 ms 2936 KB Output is correct
12 Correct 12 ms 3576 KB Output is correct
13 Correct 12 ms 3704 KB Output is correct
14 Correct 5 ms 2808 KB Output is correct
15 Correct 6 ms 2936 KB Output is correct
16 Correct 1224 ms 97240 KB Output is correct
17 Correct 162 ms 20108 KB Output is correct
18 Correct 207 ms 22768 KB Output is correct
19 Correct 1576 ms 101924 KB Output is correct
20 Correct 771 ms 75936 KB Output is correct
21 Correct 76 ms 10616 KB Output is correct
22 Correct 688 ms 65260 KB Output is correct