oj.uz

Submission #1121231

# Submission time Handle Problem Language Result Execution time Memory
1121231 2024-11-28T15:31:21 Z LonlyR Cities (BOI16_cities) C++17
74 / 100
 6000 ms 245524 KB 
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()

using namespace std;
const int maxn = 1e5 + 5;
int n, k, m;
int chosen[maxn];
vector<pair<int,int>> adj[maxn];
vector<array<int, 3>> edges;
vector<int> ok;

struct sub1{
    int par[maxn];
    int root(int x)
    {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }
    bool unite(int u, int v)
    {
        if ((u = root(u)) == (v = root(v))) return 0;
        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return 1;
    }
    sub1()
    {
        sort(all(edges));
        int res = 1e18;
        for (int mask = 1; mask < 1 << n; mask++)
        {
            for (int i = 1; i <= n; i++)
                par[i] = -1;
            int ans = 0;
            for (auto i : edges)
            {
                int w = i[0], u = i[1], v = i[2];
                if ((mask >> (u - 1) & 1) && (mask >> (v - 1) & 1))
                    ans += w * unite(u, v);
            }
            int check = 0;
            for (int j = 1; j < ok.size(); j++)
                check |= unite(ok[j - 1], ok[j]);
            if (!check)
                res = min(res, ans);
        }
        cout << res;
    }
};

struct full{
    #define iii array<int, 3>
    int d[maxn][32];
    full()
    {
        priority_queue<iii, vector<iii>, greater<iii>> pq;
        memset(d, 0x3f, sizeof d);
        int oo = d[0][0];
        for (int i = 1; i <= n; i++)
        {
            int bit = 0;
            if (chosen[i])
                bit = 1 << (chosen[i] - 1);
            d[i][bit] = 0;
            pq.push({0, i, bit});
        }
        int full = (1 << k) - 1;
        while (pq.size())
        {
            auto to = pq.top();
            pq.pop();
            int val = to[0], u = to[1], bit = to[2];
            if (val != d[u][bit]) continue;
            for (auto i : adj[u])
            {
                int v, w;
                tie(v, w) = i;
                int not_mask = bit ^ full;
                if(d[v][bit] > val + w)
                    pq.push({d[v][bit] = val + w, v, bit});
                for(int s = not_mask; s > 0; s = (s - 1) & not_mask)
                    if(d[v][bit | s] > val + d[v][s] + w)
                        pq.push({d[v][bit | s] = val + d[v][s] + w, v, bit | s});
            }
        }
        int res = oo;
        for (int i = 1; i <= n; i++)
            res = min(res, d[i][full]);
        cout << res;
    }

};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> k >> m;
    for (int i = 1, x; i <= k; i++)
        cin >> x, chosen[x] = 1;
    k = accumulate(chosen + 1, chosen + n + 1, 0ll);
    for (int i = 1; i <= n; i++)
        if (chosen[i])
            ok.emplace_back(i),
            chosen[i] = ok.size();
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w,
        adj[u].emplace_back(v, w),
        adj[v].emplace_back(u, w),
        edges.push_back({w, u, v});
    if (n <= 20)
    {
        sub1 solve;
    }
    else
    {
        full solve;
    }
}

Compilation message

cities.cpp: In constructor 'sub1::sub1()':
cities.cpp:43:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for (int j = 1; j < ok.size(); j++)
      |                             ~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27732 KB Output is correct
2 Correct 138 ms 27800 KB Output is correct
3 Correct 142 ms 27896 KB Output is correct
4 Correct 150 ms 27732 KB Output is correct
5 Correct 149 ms 27740 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 75256 KB Output is correct
2 Correct 743 ms 74352 KB Output is correct
3 Correct 406 ms 44660 KB Output is correct
4 Correct 93 ms 49172 KB Output is correct
5 Correct 373 ms 58908 KB Output is correct
6 Correct 91 ms 47488 KB Output is correct
7 Correct 28 ms 28312 KB Output is correct
8 Correct 23 ms 28056 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 28744 KB Output is correct
2 Correct 31 ms 28756 KB Output is correct
3 Correct 32 ms 28436 KB Output is correct
4 Correct 37 ms 28944 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2832 ms 149056 KB Output is correct
2 Correct 2539 ms 148364 KB Output is correct
3 Correct 1293 ms 64288 KB Output is correct
4 Correct 1730 ms 100076 KB Output is correct
5 Correct 367 ms 73584 KB Output is correct
6 Correct 174 ms 54260 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6042 ms 245524 KB Time limit exceeded
2 Halted 0 ms 0 KB -