Submission #1268917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268917		ducanh0811	Cities (BOI16_cities)	C++20	0 / 100	2538 ms	124988 KiB

cities

#include <bits/stdc++.h>
#define int long long
#define MASK(i) (1 << (i))
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

int n, k, m;
#define MAXK 5
#define MAXN 100005
#define MAXM 200005
const int INF = 1e18;
int cities[MAXK];

struct Graph {
    int n;
    vector<vector<pair<int, int>>> g;
    vector<int> nodeList;
    vector<int> visited;
    Graph(int _n = 0) : n(_n){
        g.assign(n + 2, {});
        visited.assign(n + 2, false);
        nodeList = vector<int>();
    }

    void addEdge(int u, int v, int w){
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
        if (!visited[u]) visited[u] = 1, nodeList.push_back(u);
        if (!visited[v]) visited[v] = 1, nodeList.push_back(v);
    }
} g;

pair<int, Graph> mst[MASK(MAXK)];

int vi[MAXN];
int timer = 0;
int par[MAXN];
int dist[MAXN];

pair<int, Graph> process(Graph &fullGraph, int finalPoint, int prevValue, int oldValue){
    vector<int> &nodeList = fullGraph.nodeList;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    timer++;
    FOR(i, 1, n) dist[i] = INF;
    assert(nodeList.size() != 0);
    for (int &i : nodeList){
        dist[i] = 0;
        pq.push(make_pair(0, i));
    }
    assert(pq.size() != 0);
    while (pq.size()){
        int oldW, u; tie(oldW, u) = pq.top();
        pq.pop();
        if (vi[u] == timer) continue;
        vi[u] = timer;
        for (pair<int, int> &x : g.g[u]){
            int v, curW; tie(v, curW) = x;
            if (dist[v] > curW + oldW){
                dist[v] = curW + oldW;
                par[v] = u;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    assert(dist[finalPoint] <= 1e16);
    int firstVal = dist[finalPoint] + oldValue;
    if (firstVal > prevValue) return make_pair(INF, Graph(0));
    Graph secondVal = fullGraph;
    while (dist[finalPoint] != 0){
        int prevNode = par[finalPoint];
        secondVal.addEdge(prevNode, finalPoint, -1);
        finalPoint = prevNode;
    }
    return make_pair(firstVal, secondVal);
}

void solve(){
    cin >> n >> k >> m;
    FOR(i, 0, k - 1) cin >> cities[i];
    g = Graph(n);
    FOR(i, 1, m){
        int x, y, w; cin >> x >> y >> w;
        g.addEdge(x, y, w);
    }
    FOR(mask, 0, MASK(k) - 1){
        mst[mask].first = INF;
        mst[mask].second = Graph(n);
    }
    FOR(i, 0, k - 1){
        mst[MASK(i)].first = 0;
        mst[MASK(i)].second.addEdge(cities[i], cities[i], -1);
//        cout << mst[MASK(i)].second.nodeList[0] << '\n';
    }
    FOR(mask, 0, MASK(k) - 1){
        if (__builtin_popcount(mask) <= 1) continue;
        vector<int> bits;
        for (int subMask = mask; subMask > 0; subMask -= subMask & -subMask){
            int curBit = __builtin_ctz(subMask);
            bits.push_back(curBit);
        }
        for (int &x : bits){
            int prevMask = mask ^ MASK(x);
//            cout << "? OK: " << bitset<5>(prevMask) << " " << bitset<5>(mask) << '\n';
//            cout << x << ' ' << cities[x] << '\n';
//            cout << "final city: " << cities[x] << '\n';
            pair<int, Graph> tmpVal = process(mst[prevMask].second, cities[x], mst[mask].first, mst[prevMask].first);
            if (mst[mask].first > tmpVal.first){
                mst[mask] = tmpVal;
            }
        }
    }
    cout << mst[MASK(k) - 1].first;
}

#define task ""
int32_t main(){
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int32_t main()':
cities.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26