oj.uz

답안 #444772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444772 2021-07-15T08:10:07 Z Nihal_9936 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 1811 ms 174552 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,INF));
 
        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])if(not v[i[0]]){
 
                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 2 ms 460 KB Output is correct
5 Correct 2 ms 588 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

# 결과 실행 시간 메모리 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 588 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 5 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 1900 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 2 ms 460 KB Output is correct
5 Correct 2 ms 588 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 5 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 1900 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 1513 ms 156004 KB Output is correct
17 Correct 197 ms 41028 KB Output is correct
18 Correct 254 ms 43716 KB Output is correct
19 Correct 1811 ms 174552 KB Output is correct
20 Correct 525 ms 129496 KB Output is correct
21 Correct 76 ms 17480 KB Output is correct
22 Correct 576 ms 126636 KB Output is correct