Submission #1119350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119350		mariaclara	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5077 ms	10652 KiB

reconstruction

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
const int MAXN = 1e5+5;
#define W(x) get<0>(x)
#define U(x) get<1>(x)
#define V(x) get<2>(x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back 
#define fr first 
#define sc second 

int n, m, q, remov[MAXN], add[MAXN], pai[505], tam[505], cnt;
vector<trio> edges;
vector<vector<pii>> graph;

int dfs(int no, int fim, int pai, int ind, int flag) {
    if(no == fim) return ind;

    for(auto [viz, i] : graph[no]) {
        if(viz == pai) continue;
        int new_ind = ind;
        if(W(edges[i])*flag < W(edges[ind])*flag) new_ind = i;
        
        int ret = dfs(viz, fim, no, new_ind, flag);
        if(ret != -1) return ret;
    }

    return -1;
}

int find(int x) {
    int root = x, aux;

    while(pai[root] != root) {
        root = pai[root];
    }

    while(x != root) {
        aux = pai[x];
        pai[x] = root;
        x = aux;
    }

    return root;
}

bool join(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return 0;

    if(tam[x] <= tam[y]) {
        pai[x] = y;
        tam[y] += tam[x];
    }
    else {
        pai[y] = x;
        tam[x] += tam[y];
    }

    cnt++;
    return 1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);

    cin >> n >> m;

    vector<int> active;

    for(int i = 0, a, b, w; i < m; i++) {
        cin >> a >> b >> w;
        edges.pb({w,a,b});
        active.pb(i);
    }

    sort(all(edges));
    // graph.resize(n+1);

    // for(int i = 0; i < m; i++) {
    //     auto [w, a, b] = edges[i];

    //     // se existe um caminho entre a e b
    //     // removemos a menor aresta nele

    //     int sub = dfs(a, b, 0, i, 1);
    //     graph[a].pb({b, i});
    //     graph[b].pb({a, i});

    //     remov[i] = sub;
        
    //     if(sub == -1)  continue;

    //     auto [w1, a1, b1] = edges[sub];

    //     for(int j = 0; j < sz(graph[a1]); j++)
    //         if(graph[a1][j].sc == sub) {
    //             graph[a1].erase({graph[a1].begin() + j});
    //             break;
    //         }

    //     for(int j = 0; j < sz(graph[b1]); j++)
    //         if(graph[b1][j].sc == sub) {
    //             graph[b1].erase({graph[b1].begin() + j});
    //             break;
    //         }
    // }

    // graph.clear();
    // graph.resize(n+1);
    // set<int> active;

    // for(int i = m-1; i >= 0; i--) {
    //     auto [w, a, b] = edges[i];

    //     // se existe um caminho entre a e b
    //     // removemos a menor aresta nele

    //     int sub = dfs(a, b, 0, i, -1);
    //     graph[a].pb({b, i});
    //     graph[b].pb({a, i});
    //     active.insert(i);
    //     add[i] = sub;
        
    //     if(sub == -1)  continue;
    //     active.erase(sub);

    //     auto [w1, a1, b1] = edges[sub];

    //     for(int j = 0; j < sz(graph[a1]); j++)
    //         if(graph[a1][j].sc == sub) {
    //             graph[a1].erase({graph[a1].begin() + j});
    //             break;
    //         }

    //     for(int j = 0; j < sz(graph[b1]); j++)
    //         if(graph[b1][j].sc == sub) {
    //             graph[b1].erase({graph[b1].begin() + j});
    //             break;
    //         }
    // }

    cin >> q;

    int ptr = 0, w;
    while(q--) {
        cin >> w;

        // while(ptr < m and W(edges[ptr]) <= w) {
        //     if(add[ptr] != -1) active.insert(add[ptr]);
        //     if(remov[ptr] != -1) active.erase(remov[ptr]);
        //     ptr++;
        // }

        for(int i = 1; i <= n; i++) pai[i] = i, tam[i] = 1;

        vector<trio> pos1, pos2;
        for(auto it : active) {
            if(W(edges[it]) <= w) pos1.pb(edges[it]);
            else pos2.pb(edges[it]);
        }
        reverse(all(pos1));

        ll ans = 0;
        int i = 0, j = 0;
        cnt = 0;
        
        while(i < sz(pos1) and j < sz(pos2) and cnt+1 < n) {
            auto [w1, a1, b1] = pos1[i];
            auto [w2, a2, b2] = pos2[j];

            if(w - w1 <= w2 - w) ans += (w - w1) * join(a1, b1), i++;
            else ans += (w2 - w) * join(a2, b2), j++;
        }

        while(i < sz(pos1) and cnt+1 < n) ans += (w - W(pos1[i])) * join(U(pos1[i]), V(pos1[i])), i++;
        while(j < sz(pos2) and cnt+1 < n) ans += (W(pos2[j]) - w) * join(U(pos2[j]), V(pos2[j])), j++;
        cout << ans << endl;
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:154:9: warning: unused variable 'ptr' [-Wunused-variable]
  154 |     int ptr = 0, w;
      |         ^~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23