oj.uz

Submission #559807

# Submission time Handle Problem Language Result Execution time Memory
559807 2022-05-10T15:45:49 Z tamthegod Cities (BOI16_cities) C++14
100 / 100
 3477 ms 74740 KB 
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<cstdio>
#include<bitset>
#include<chrono>
#include<random>
#include<ext/rope>
/* ordered_set
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e17;
int n, m, k;
int d[maxN];
int f[maxN][1 << 6];
struct TPQRec
{
    int vertex, dlab;
    bool operator < (const TPQRec& other) const
    {
        return other.dlab < dlab;
    }
    bool Valid() const
    {
        return d[vertex] == dlab;
    }
};
struct TAdj
{
    int v, w;
};
vector<TAdj> adj[maxN];
vector<int> imp;
void ReadInput()
{
    cin >> n >> k >> m;
    for(int i=1; i<=k; i++)
    {
        int x;
        cin >> x;
        imp.pb(x);
    }
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
}
void Dijkstra()
{
    priority_queue<TPQRec> pq;
    for(int i=1; i<=n; i++)
        if(d[i] < oo) pq.push({i, d[i]});
    while(!pq.empty())
    {
        TPQRec r = pq.top();
        pq.pop();
        if(!r.Valid()) continue;
        int u = r.vertex;
        for(TAdj a : adj[u])
        {
            if(d[a.v] > d[u] + a.w)
            {
                d[a.v] = d[u] + a.w;
                pq.push({a.v, d[a.v]});
            }
        }
    }
}
void Solve()
{
    memset(f, 3, sizeof f);
    for(int i=0; i<k; i++)
        f[imp[i]][1 << i] = 0;
    for(int mask=0; mask<(1<<k); mask++)
    {
        for(int mask1=0; mask1<(1<<k); mask1++)
            for(int mask2=0; mask2<(1<<k); mask2++)
            {
                if((mask1 | mask2) != mask) continue;
                for(int i=1; i<=n; i++)
                    f[i][mask] = min(f[i][mask], f[i][mask1] + f[i][mask2]);
            }
        for(int i=1; i<=n; i++) d[i] = f[i][mask];
        Dijkstra();
        for(int i=1; i<=n; i++) f[i][mask] = d[i];
    }
    int res = oo;
    for(int i=1; i<=n; i++) res = min(res, f[i][(1 << k) - 1]);
    cout << res;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 52692 KB Output is correct
2 Correct 30 ms 52736 KB Output is correct
3 Correct 24 ms 52736 KB Output is correct
4 Correct 24 ms 52684 KB Output is correct
5 Correct 24 ms 52728 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 74452 KB Output is correct
2 Correct 579 ms 73940 KB Output is correct
3 Correct 371 ms 64668 KB Output is correct
4 Correct 92 ms 65276 KB Output is correct
5 Correct 333 ms 72316 KB Output is correct
6 Correct 106 ms 65228 KB Output is correct
7 Correct 25 ms 52880 KB Output is correct
8 Correct 31 ms 52860 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 52860 KB Output is correct
2 Correct 28 ms 52864 KB Output is correct
3 Correct 26 ms 52820 KB Output is correct
4 Correct 26 ms 52876 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 74564 KB Output is correct
2 Correct 1344 ms 74112 KB Output is correct
3 Correct 1004 ms 64668 KB Output is correct
4 Correct 771 ms 71400 KB Output is correct
5 Correct 198 ms 66544 KB Output is correct
6 Correct 95 ms 67324 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3400 ms 74740 KB Output is correct
2 Correct 3477 ms 74544 KB Output is correct
3 Correct 3344 ms 74080 KB Output is correct
4 Correct 2664 ms 64764 KB Output is correct
5 Correct 1736 ms 71424 KB Output is correct
6 Correct 308 ms 66640 KB Output is correct
7 Correct 118 ms 67540 KB Output is correct