oj.uz

Submission #637900

# Submission time Handle Problem Language Result Execution time Memory
637900 2022-09-03T14:21:54 Z Cross_Ratio Reconstruction Project (JOI22_reconstruction) C++14
3 / 100
 5000 ms 22780 KB 
#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;
    adj.resize(N);
    int i, j;
    for(i=0;i<M;i++) {
        int a, b, c;
        cin >> a>>b>>c;
        Edge[i] = {c, a-1, b-1, i};
    }
    sort(Edge, Edge+M);
    UnionFind UF(N);
    for(i=0;i<M;i++) {
        Edge[i][3] = i;
        if(UF.Find(Edge[i][1])==UF.Find(Edge[i][2])) continue;
        UF.Merge(Edge[i][1], Edge[i][2]);
        Tree[0].push_back(Edge[i]);
        S[i] = true;
        adj[Edge[i][1]].insert({Edge[i][2], Edge[i][0], i});
        adj[Edge[i][2]].insert({Edge[i][1], Edge[i][0], i});
    }
    int cnt = 0;
    ll time = 0;
    C[cnt] = 0;
    for(auto it : Tree[0]) {
        A[0]--;
        B[0] += it[0];
    }
    while(true) {
        cnt++;
        int i, j;
        for(i=0;i<N;i++) {
            for(j=0;j<N;j++) dis[i][j] = INF;
        }
        for(i=0;i<N;i++) {
            dfs(i, -1, i);
        }
        ll id = -1, ti = INF, id2 = -1;
        for(i=0;i<M;i++) {
            if(!S[i]) {
                ll mi = dis[Edge[i][1]][Edge[i][2]];
                if(mi < Edge[i][0] && time < Edge[i][0]) {
                    ll t2 = (mi+Edge[i][0]+1)/2;
                    if(time > t2) continue;
                    if(t2 < ti) {
                        ti = t2;
                        id = i;
                        id2 = dis2[Edge[i][1]][Edge[i][2]];
                    }
                }
            }
        }
        //cout << id << ' ' << ti << ' ' << id2 << '\n';
        ll t3 = INF;
        for(auto it : Tree[cnt-1]) {
            if(it[0]>time) t3 = min(t3, it[0]);
        }
        if(t3 != INF && t3 < ti) {
            C[cnt] = t3;
            Tree[cnt] = Tree[cnt-1];
            time = t3;
            for(auto it : Tree[cnt-1]) {
                if(it[0]<=time) {
                    A[cnt]++;
                    B[cnt] -= it[0];
                }
                else {
                    A[cnt]--;
                    B[cnt] += it[0];
                }
            }
            //cout << C[cnt] << " : " << A[cnt] << ' '<< B[cnt] << '\n';
            time = t3;
            continue;
        }
        if(id==-1) {
            C[cnt] = INF;
            break;
        }
        C[cnt] = ti;
        S[id] = true;
        S[id2] = false;
        adj[Edge[id2][1]].erase({Edge[id2][2], Edge[id2][0], id2});
        adj[Edge[id2][2]].erase({Edge[id2][1], Edge[id2][0], id2});
        adj[Edge[id][1]].insert({Edge[id][2], Edge[id][0], id});
        adj[Edge[id][2]].insert({Edge[id][1], Edge[id][0], id});
        for(auto it : Tree[cnt-1]) {
            if(it[3]!=id2) Tree[cnt].push_back(it);
        }
        Tree[cnt].push_back(Edge[id]);
        time = ti;
        for(auto it : Tree[cnt]) {
            //cout << it[0] << ' ' << it[1] << ' ' << it[2] << ' ' << it[3] << '\n';
            if(it[0]<=time) {
                A[cnt]++;
                B[cnt] -= it[0];
            }
            else {
                A[cnt]--;
                B[cnt] += it[0];
            }
        }
        //cout << C[cnt] << " : " << A[cnt] << ' '<< B[cnt] << '\n';
    }
    for(i=0;i<=cnt;i++) {
        //cout << C[i] << " : " << A[i] <<' ' << B[i] << '\n';
    }
    int Q;
    cin >> Q;
    int ct = 0;
    while(Q--) {
        ll x;
        cin >> x;
        while(x>=C[ct+1]) ct++;
        ll ans = 0;
        cout << x * A[ct] + B[ct] << '\n';
    }
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:164:12: warning: unused variable 'ans' [-Wunused-variable]
  164 |         ll ans = 0;
      |            ^~~
reconstruction.cpp:54:12: warning: unused variable 'j' [-Wunused-variable]
   54 |     int i, j;
      |            ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 480 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 480 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Execution timed out 5079 ms 20912 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Execution timed out 5071 ms 22780 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 480 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Execution timed out 5083 ms 18840 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 480 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Execution timed out 5079 ms 20912 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 480 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Execution timed out 5079 ms 20912 KB Time limit exceeded
21 Halted 0 ms 0 KB -