Submission #637909

#	Time	Username	Problem	Language	Result	Execution time	Memory
637909		Cross_Ratio	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	5058 ms	9488 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll A[2005];
ll B[2005];
ll C[2005]; // C[i] <= x < C[i+1], ans = x * A[i] + B[i];
typedef pair<ll, ll> P;
ll dis[505][505];
ll dis2[505][505];
struct UnionFind {
    vector<int> root;
    UnionFind(int n) {
        root.resize(n);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if(x==y) return;
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
vector<array<ll, 4>> Tree[2005];
vector<set<array<ll, 4>>> adj;
array<ll, 4> Edge[100005];
bool S[100005];
void dfs(int c, int p, int rt) {
    for(auto n2 : adj[c]) {
        if(n2[0]==p) continue;
        dis[rt][n2[0]] = dis[rt][c];
        dis2[rt][n2[0]] = dis2[rt][c];
        if(dis[rt][n2[0]] > n2[1]) {
            dis[rt][n2[0]] = n2[1];
            dis2[rt][n2[0]] = n2[2];
        }
        dfs(n2[0], c, rt);
    }
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    clock_t st = clock();
    adj.resize(N);
    int i, j;
    for(i=0;i<M;i++) {
        int a, b, c;
        cin >> a>>b>>c;
        //a = rand() % N + 1;
        //b = rand() % N+ 1;
        //c = rand();
        Edge[i] = {c, a-1, b-1, i};
    }
    sort(Edge, Edge+M);
    int Q;
    cin >> Q;
    while(Q--) {
        ll x;
        ll ans = 0;
        cin >> x;
        vector<array<int, 4>> Edge2;
        for(i=0;i<M;i++) Edge2.push_back({abs(Edge[i][0]-x), Edge[i][1], Edge[i][2], Edge[i][3]});
        sort(Edge2.begin(), Edge2.end());
        UnionFind UF(N);
        for(i=0;i<M;i++) {
            if(UF.Find(Edge2[i][1])==UF.Find(Edge2[i][2])) continue;
            UF.Merge(Edge2[i][1], Edge2[i][2]);
            ans += Edge2[i][0];
        }
        cout << ans << '\n';
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:72:46: warning: narrowing conversion of 'std::abs((Edge[i].std::array<long long int, 4>::operator[](0) - x))' from 'long long int' to 'int' [-Wnarrowing]
   72 |         for(i=0;i<M;i++) Edge2.push_back({abs(Edge[i][0]-x), Edge[i][1], Edge[i][2], Edge[i][3]});
      |                                           ~~~^~~~~~~~~~~~~~
reconstruction.cpp:72:97: warning: narrowing conversion of 'Edge[i].std::array<long long int, 4>::operator[](1)' from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   72 |         for(i=0;i<M;i++) Edge2.push_back({abs(Edge[i][0]-x), Edge[i][1], Edge[i][2], Edge[i][3]});
      |                                                                                                 ^
reconstruction.cpp:72:97: warning: narrowing conversion of 'Edge[i].std::array<long long int, 4>::operator[](2)' from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
reconstruction.cpp:72:97: warning: narrowing conversion of 'Edge[i].std::array<long long int, 4>::operator[](3)' from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
reconstruction.cpp:53:13: warning: unused variable 'st' [-Wunused-variable]
   53 |     clock_t st = clock();
      |             ^~
reconstruction.cpp:55:12: warning: unused variable 'j' [-Wunused-variable]
   55 |     int i, j;
      |            ^

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