oj.uz

답안 #444774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444774 2021-07-15T08:13:17 Z Nihal_9936 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 1827 ms 169548 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));
 
 
signed travel_plan(signed n,signed m,signed r[][2],signed l[],signed k,signed 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];
 
 
 
 
}
 
 
 
// void code(){
//             int r,l,k,p;
//             cin>>n>>m;
            
            
// }
 
 
// signed main()
// {
//      ios_base::sync_with_stdio(false);
//      cin.tie(0); cout.tie(0);
   
//    // freopen("spainting.in", "r", stdin);
//    // freopen("spainting.out", "w", stdout);
 
//    int t = 1;
//    // cin>>t;
//    while(t--) code();
//    return 0;
// }

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

# 결과 실행 시간 메모리 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 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 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

# 결과 실행 시간 메모리 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 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 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 4 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

# 결과 실행 시간 메모리 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 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 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 4 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 1448 ms 152968 KB Output is correct
17 Correct 178 ms 39036 KB Output is correct
18 Correct 241 ms 41768 KB Output is correct
19 Correct 1827 ms 169548 KB Output is correct
20 Correct 525 ms 129564 KB Output is correct
21 Correct 73 ms 16836 KB Output is correct
22 Correct 575 ms 126092 KB Output is correct