Submission #637923

#	Time	Username	Problem	Language	Result	Execution time	Memory
637923		Cross_Ratio	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	725 ms	30692 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];
vector<vector<array<int, 2>>> E;
vector<array<int, 3>> E2;
ll val[505];
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;
    E.resize(N);
    for(i=0;i<M;i++) {
        int a, b, c;
        cin >> a>>b>>c;
        if(a>b) swap(a, b);
        E[a-1].push_back({c, i});
        Edge[i] = {c, a-1, b-1, i};
    }
    for(i=0;i<N-1;i++) {
        sort(E[i].begin(),E[i].end());
        val[i] = E[i][0][0];
        for(j=0;j+1<E[i].size();j++) {
            ll time = (E[i][j][0] + E[i][j+1][0] + 1) / 2;
            E2.push_back({time, i, E[i][j+1][0]});
        }
    }
    sort(E2.begin(),E2.end());
    int Q;
    cin >> Q;
    int pt = -1;
    while(Q--) {
        ll x;
        ll ans = 0;
        cin >> x;
        while(pt+1<E2.size()&&x>=E2[pt+1][0]) {
            pt++;
            val[E2[pt][1]] = E2[pt][2];
        }
        for(i=0;i<N-1;i++) ans += abs(x - val[i]);
        cout << ans << '\n';
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(j=0;j+1<E[i].size();j++) {
      |                 ~~~^~~~~~~~~~~~
reconstruction.cpp:60:27: warning: narrowing conversion of 'time' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   60 |             E2.push_back({time, i, E[i][j+1][0]});
      |                           ^~~~
reconstruction.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while(pt+1<E2.size()&&x>=E2[pt+1][0]) {
      |               ~~~~^~~~~~~~~~
reconstruction.cpp:44:13: warning: unused variable 'st' [-Wunused-variable]
   44 |     clock_t st = clock();
      |             ^~

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