oj.uz

Submission #444776

# Submission time Handle Problem Language Result Execution time Memory
444776 2021-07-15T08:20:23 Z Nihal_9936 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1783 ms 169624 KB 
#include <bits/stdc++.h>
using namespace std;
#include "crocodile.h"
 
 
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& a) { return in >> a.first >> a.second; }
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> a) { return out << a.first << " " << a.second;}
template<typename T> void print(T t) { cout << t <<' '; }
template<typename T, typename... Args> void print(T t, Args... args) { print(t);print(args...); }
string operator*=(string& s, int cnt) { string t = s;for (size_t i = 1; i < cnt; i++)s += t;return s; }
string operator*(string s, int cnt) { return s *= cnt; }
 
 
// #define int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define allr(x)           (x).rbegin(),(x).rend()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define len(x)             (int)((x).size())
#define elif              else if
#define add               insert
#define append            push_back
#define pop               pop_back 
#define str               string
#define in                :
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define vi                vector<int>
#define vii               vector<pii>
#define mi                map<int,int>
#define mii               map<pii,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define rrep(i,a,b)       for(int i=a;i>b;i--)
#define el                 '\n'
#define printl(arg) cout << arg << endl
// #define print(arg) cout << arg
#define inputa(arg) for (auto& e : arg) cin >> e
#define printa(arg) for (auto& e : arg) print(e);
#define printr(arg) { printl(arg);return; }
#define printd(arg) printf("%0.15lf\n", arg)
 
 
const int mod=1e9+7;
// const int INF=1e18;
const int MAX_N=2e5+2;
 
 
int n,m,k,x,y,z,t,q,counter;
// vector<vector<vector<int>>> dp(101 , vector<vector<int>>(101, vector<int>(101)));
// vector<vector<int>>dp(5001, vi(5001)),ndp(5001,vi(5001));
 
 
int travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
 
        vector<vector<vector<int>>> a(n);
 
        rep(i,0,m){
            int x=r[i][0], y=r[i][1],z=l[i];
            a[x].append({y,z});
            a[y].append({x,z});
        }
 
        vi v(n,0);
        vector<vector<int>> dis(n,vector<int>(2,INT_MAX));
 
        set<pii> dq;
 
        rep(i,0,k){
            int t=p[i];
            dis[t]={0,0};
            dq.add({0,t});
        }
 
        while(len(dq)){
 
            pii tt=*dq.begin();
            int par=tt.sc;
            dq.erase(dq.begin());
 
            if (v[par]) continue;
            v[par]=1;
 
            for(auto& i in a[par]){
 
                int d=i[1],child=i[0];
 
                if(d+dis[par][1]<dis[child][1]){
                    if(d+dis[par][1]<=dis[child][0]){
 
                        dis[child]={d+dis[par][1],dis[child][0]};
 
                    }else{
 
                        dis[child]={dis[child][0],d+dis[par][1]};
                    }
 
                    dq.add({dis[child][1],child});
                }
 
            }
 
        }   
 
        return dis[0][1];
 
 
 
 
}

Compilation message

crocodile.cpp: In function 'std::string operator*=(std::string&, int)':
crocodile.cpp:10:75: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | string operator*=(string& s, int cnt) { string t = s;for (size_t i = 1; i < cnt; i++)s += t;return s; }
      |                                                                         ~~^~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 6 ms 1740 KB Output is correct
13 Correct 5 ms 1868 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 588 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 6 ms 1740 KB Output is correct
13 Correct 5 ms 1868 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 1446 ms 153056 KB Output is correct
17 Correct 181 ms 39000 KB Output is correct
18 Correct 244 ms 41728 KB Output is correct
19 Correct 1783 ms 169624 KB Output is correct
20 Correct 530 ms 129512 KB Output is correct
21 Correct 72 ms 16836 KB Output is correct
22 Correct 571 ms 126088 KB Output is correct