oj.uz

Submission #679093

# Submission time Handle Problem Language Result Execution time Memory
679093 2023-01-07T12:17:23 Z Cross_Ratio Bridges (APIO19_bridges) C++14
100 / 100
 2839 ms 17540 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int INF = 2e9;
struct UnionFind {
    vector<int> root;
    vector<array<int, 4>> V;
    bool mode;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
        mode = false;
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        if(!mode) root[n] = r;
        return r;
    }
    int Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if(x==y) return 0;
        if(root[x]>root[y]) swap(x, y);
        if(mode) V.push_back({x, root[x], y, root[y]});
        root[x] += root[y];
        root[y] = x;
        return 1;
    }
    void rollback() {
        if(V.size()==0) return;
        auto it = V.back();
        root[it[0]] = it[1], root[it[2]] = it[3];
        V.pop_back();
    }
};
int A[100005];
int B[100005];
int C[100005];
int D[100005];
array<int, 3> Query[100005];
int ans[100005];
int sB = 2000;
bool chan[100005];
int N, M;
vector<array<int, 2>> idx2;
vector<int> idx;
int id(int n) {
    return lower_bound(idx.begin(),idx.end(),n)-idx.begin();
}
clock_t sttime;
void calc(int s, int e) {
    int i, j;
    for(i=s;i<e;i++) {
        if(Query[i][0]==1) {
            chan[Query[i][1]] = true;
        }
    }
    idx.clear();
    for(i=0;i<M;i++) {
        if(!chan[idx2[i][1]]) idx.push_back(idx2[i][0]);
    }
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    vector<vector<int>> V1, V2;
    V1.resize(idx.size()+1);
    V2.resize(idx.size()+1);
    vector<int> E;
    for(i=0;i<M;i++) {
        if(!chan[i]) {
            V1[lower_bound(idx.begin(),idx.end(),C[i])-idx.begin()].push_back(i);
        }
        else E.push_back(i);
    }
    vector<array<int, 3>> F;
    for(i=s;i<e;i++) {
        if(Query[i][0]==2) {
            V2[lower_bound(idx.begin(),idx.end(),Query[i][2])-idx.begin()].push_back(i);
        }
        else F.push_back({i, Query[i][1], Query[i][2]});
    }
    UnionFind UF(N);
    int pv = e+1, st = -1;
    for(i=idx.size();i>=0;i--) {
        for(int k : V1[i]) {
            UF.Merge(A[k], B[k]);
            pv = e+1, st = -1;
        }
        sort(V2[i].begin(),V2[i].end());
        for(int k : V2[i]) {
            if(pv > k) {
                for(int v : E) {
                    D[v] = C[v];
                }
                for(j=0;j<F.size();j++) {
                    if(F[j][0] < k) D[F[j][1]] = F[j][2];
                    else {
                        break;
                    }
                }
                st = j;
            }
            else {
                for(j = st; j < F.size();j++) {
                    if(F[j][0]<k) D[F[j][1]] = F[j][2];
                    else {
                        break;
                    }
                }
                st = j;
            }
            pv = k;
            int sum = 0;
            UF.mode = true;
            for(int v : E) {
                if(Query[k][2] <= D[v]) {
                    sum += UF.Merge(A[v], B[v]);
                }
            }
            ans[k] = -UF.root[UF.Find(Query[k][1])];
            while(sum--) {
                UF.rollback();
            }
            UF.mode = false;
        }
    }
    for(i=s;i<e;i++) {
        if(Query[i][0]==1) C[Query[i][1]] = Query[i][2];
    }
    vector<array<int, 2>> V5, V6;
    for(i=0;i<M;i++) {
        if(idx2[i][0]==C[idx2[i][1]]) V5.push_back(idx2[i]);
        else V6.push_back({C[idx2[i][1]], idx2[i][1]});
    }
    sort(V6.begin(),V6.end());
    idx2.clear();
    idx2.resize(M);
    for(i=0;i+1<V5.size();i++) {
        assert(V5[i][0]<=V5[i+1][0]);
    }
    merge(V5.begin(),V5.end(),V6.begin(),V6.end(),idx2.begin());
    for(i=0;i+1<idx2.size();i++) {
        assert(idx2[i][0]<=idx2[i+1][0]);
    }
    for(i=0;i<M;i++) chan[i] = false;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    int i, j;
    sttime = clock();
    for(i=0;i<M;i++) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--, B[i]--;
    }
    int Q;
    cin >> Q;
    int cnt1 = 0;
    for(i=0;i<Q;i++) {
        cin >> Query[i][0] >> Query[i][1] >> Query[i][2];
        Query[i][1]--;
        if(Query[i][0]==1) cnt1++;
    }
    for(i=0;i<M;i++) idx2.push_back({C[i], i});
    sort(idx2.begin(),idx2.end());
    int pt = 0;
    for(i=0;i<Q;i++) {
        if(i-pt+1==sB||i==Q-1) {
            calc(pt, i+1);
            pt = i+1;
        }
    }
    for(i=0;i<Q;i++) {
        if(Query[i][0]==2) cout << ans[i] << '\n';
    }
}

Compilation message

bridges.cpp: In function 'void calc(int, int)':
bridges.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 for(j=0;j<F.size();j++) {
      |                         ~^~~~~~~~~
bridges.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |                 for(j = st; j < F.size();j++) {
      |                             ~~^~~~~~~~~~
bridges.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(i=0;i+1<V5.size();i++) {
      |             ~~~^~~~~~~~~~
bridges.cpp:142:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(i=0;i+1<idx2.size();i++) {
      |             ~~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:152:12: warning: unused variable 'j' [-Wunused-variable]
  152 |     int i, j;
      |            ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 27 ms 624 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 8 ms 520 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 9 ms 468 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 8 ms 468 KB Output is correct
11 Correct 9 ms 540 KB Output is correct
12 Correct 9 ms 548 KB Output is correct
13 Correct 12 ms 468 KB Output is correct
14 Correct 11 ms 544 KB Output is correct
15 Correct 13 ms 536 KB Output is correct
16 Correct 9 ms 468 KB Output is correct
17 Correct 9 ms 468 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1837 ms 8336 KB Output is correct
2 Correct 1699 ms 8604 KB Output is correct
3 Correct 1684 ms 8480 KB Output is correct
4 Correct 1708 ms 8516 KB Output is correct
5 Correct 1818 ms 8400 KB Output is correct
6 Correct 2291 ms 8840 KB Output is correct
7 Correct 2168 ms 8960 KB Output is correct
8 Correct 2057 ms 8864 KB Output is correct
9 Correct 29 ms 2132 KB Output is correct
10 Correct 1177 ms 4900 KB Output is correct
11 Correct 1056 ms 4940 KB Output is correct
12 Correct 1225 ms 9132 KB Output is correct
13 Correct 1167 ms 8584 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 6408 KB Output is correct
2 Correct 920 ms 3416 KB Output is correct
3 Correct 1411 ms 6460 KB Output is correct
4 Correct 1330 ms 6464 KB Output is correct
5 Correct 37 ms 2124 KB Output is correct
6 Correct 1447 ms 6548 KB Output is correct
7 Correct 1222 ms 6504 KB Output is correct
8 Correct 1052 ms 6584 KB Output is correct
9 Correct 798 ms 6708 KB Output is correct
10 Correct 706 ms 6620 KB Output is correct
11 Correct 811 ms 6276 KB Output is correct
12 Correct 703 ms 6412 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1698 ms 15096 KB Output is correct
2 Correct 28 ms 2228 KB Output is correct
3 Correct 185 ms 12724 KB Output is correct
4 Correct 61 ms 5552 KB Output is correct
5 Correct 322 ms 7120 KB Output is correct
6 Correct 1624 ms 14884 KB Output is correct
7 Correct 328 ms 7044 KB Output is correct
8 Correct 709 ms 8708 KB Output is correct
9 Correct 740 ms 8712 KB Output is correct
10 Correct 745 ms 8760 KB Output is correct
11 Correct 1187 ms 12048 KB Output is correct
12 Correct 1141 ms 12056 KB Output is correct
13 Correct 1167 ms 12252 KB Output is correct
14 Correct 284 ms 7024 KB Output is correct
15 Correct 319 ms 7252 KB Output is correct
16 Correct 1562 ms 14848 KB Output is correct
17 Correct 1724 ms 14904 KB Output is correct
18 Correct 1685 ms 17040 KB Output is correct
19 Correct 1703 ms 17084 KB Output is correct
20 Correct 1312 ms 15476 KB Output is correct
21 Correct 1407 ms 15520 KB Output is correct
22 Correct 1513 ms 16756 KB Output is correct
23 Correct 478 ms 8268 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1837 ms 8336 KB Output is correct
2 Correct 1699 ms 8604 KB Output is correct
3 Correct 1684 ms 8480 KB Output is correct
4 Correct 1708 ms 8516 KB Output is correct
5 Correct 1818 ms 8400 KB Output is correct
6 Correct 2291 ms 8840 KB Output is correct
7 Correct 2168 ms 8960 KB Output is correct
8 Correct 2057 ms 8864 KB Output is correct
9 Correct 29 ms 2132 KB Output is correct
10 Correct 1177 ms 4900 KB Output is correct
11 Correct 1056 ms 4940 KB Output is correct
12 Correct 1225 ms 9132 KB Output is correct
13 Correct 1167 ms 8584 KB Output is correct
14 Correct 1366 ms 6408 KB Output is correct
15 Correct 920 ms 3416 KB Output is correct
16 Correct 1411 ms 6460 KB Output is correct
17 Correct 1330 ms 6464 KB Output is correct
18 Correct 37 ms 2124 KB Output is correct
19 Correct 1447 ms 6548 KB Output is correct
20 Correct 1222 ms 6504 KB Output is correct
21 Correct 1052 ms 6584 KB Output is correct
22 Correct 798 ms 6708 KB Output is correct
23 Correct 706 ms 6620 KB Output is correct
24 Correct 811 ms 6276 KB Output is correct
25 Correct 703 ms 6412 KB Output is correct
26 Correct 1810 ms 8720 KB Output is correct
27 Correct 2108 ms 9204 KB Output is correct
28 Correct 1936 ms 8584 KB Output is correct
29 Correct 1281 ms 8664 KB Output is correct
30 Correct 2177 ms 8600 KB Output is correct
31 Correct 2176 ms 8588 KB Output is correct
32 Correct 2153 ms 8816 KB Output is correct
33 Correct 1920 ms 8764 KB Output is correct
34 Correct 1894 ms 8896 KB Output is correct
35 Correct 1965 ms 8788 KB Output is correct
36 Correct 1355 ms 8828 KB Output is correct
37 Correct 1349 ms 8428 KB Output is correct
38 Correct 1322 ms 8388 KB Output is correct
39 Correct 948 ms 8588 KB Output is correct
40 Correct 912 ms 8740 KB Output is correct
41 Correct 873 ms 8720 KB Output is correct
42 Correct 949 ms 8388 KB Output is correct
43 Correct 1002 ms 8240 KB Output is correct
44 Correct 989 ms 8416 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 27 ms 624 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 8 ms 520 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 9 ms 468 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 8 ms 468 KB Output is correct
11 Correct 9 ms 540 KB Output is correct
12 Correct 9 ms 548 KB Output is correct
13 Correct 12 ms 468 KB Output is correct
14 Correct 11 ms 544 KB Output is correct
15 Correct 13 ms 536 KB Output is correct
16 Correct 9 ms 468 KB Output is correct
17 Correct 9 ms 468 KB Output is correct
18 Correct 1837 ms 8336 KB Output is correct
19 Correct 1699 ms 8604 KB Output is correct
20 Correct 1684 ms 8480 KB Output is correct
21 Correct 1708 ms 8516 KB Output is correct
22 Correct 1818 ms 8400 KB Output is correct
23 Correct 2291 ms 8840 KB Output is correct
24 Correct 2168 ms 8960 KB Output is correct
25 Correct 2057 ms 8864 KB Output is correct
26 Correct 29 ms 2132 KB Output is correct
27 Correct 1177 ms 4900 KB Output is correct
28 Correct 1056 ms 4940 KB Output is correct
29 Correct 1225 ms 9132 KB Output is correct
30 Correct 1167 ms 8584 KB Output is correct
31 Correct 1366 ms 6408 KB Output is correct
32 Correct 920 ms 3416 KB Output is correct
33 Correct 1411 ms 6460 KB Output is correct
34 Correct 1330 ms 6464 KB Output is correct
35 Correct 37 ms 2124 KB Output is correct
36 Correct 1447 ms 6548 KB Output is correct
37 Correct 1222 ms 6504 KB Output is correct
38 Correct 1052 ms 6584 KB Output is correct
39 Correct 798 ms 6708 KB Output is correct
40 Correct 706 ms 6620 KB Output is correct
41 Correct 811 ms 6276 KB Output is correct
42 Correct 703 ms 6412 KB Output is correct
43 Correct 1698 ms 15096 KB Output is correct
44 Correct 28 ms 2228 KB Output is correct
45 Correct 185 ms 12724 KB Output is correct
46 Correct 61 ms 5552 KB Output is correct
47 Correct 322 ms 7120 KB Output is correct
48 Correct 1624 ms 14884 KB Output is correct
49 Correct 328 ms 7044 KB Output is correct
50 Correct 709 ms 8708 KB Output is correct
51 Correct 740 ms 8712 KB Output is correct
52 Correct 745 ms 8760 KB Output is correct
53 Correct 1187 ms 12048 KB Output is correct
54 Correct 1141 ms 12056 KB Output is correct
55 Correct 1167 ms 12252 KB Output is correct
56 Correct 284 ms 7024 KB Output is correct
57 Correct 319 ms 7252 KB Output is correct
58 Correct 1562 ms 14848 KB Output is correct
59 Correct 1724 ms 14904 KB Output is correct
60 Correct 1685 ms 17040 KB Output is correct
61 Correct 1703 ms 17084 KB Output is correct
62 Correct 1312 ms 15476 KB Output is correct
63 Correct 1407 ms 15520 KB Output is correct
64 Correct 1513 ms 16756 KB Output is correct
65 Correct 478 ms 8268 KB Output is correct
66 Correct 1810 ms 8720 KB Output is correct
67 Correct 2108 ms 9204 KB Output is correct
68 Correct 1936 ms 8584 KB Output is correct
69 Correct 1281 ms 8664 KB Output is correct
70 Correct 2177 ms 8600 KB Output is correct
71 Correct 2176 ms 8588 KB Output is correct
72 Correct 2153 ms 8816 KB Output is correct
73 Correct 1920 ms 8764 KB Output is correct
74 Correct 1894 ms 8896 KB Output is correct
75 Correct 1965 ms 8788 KB Output is correct
76 Correct 1355 ms 8828 KB Output is correct
77 Correct 1349 ms 8428 KB Output is correct
78 Correct 1322 ms 8388 KB Output is correct
79 Correct 948 ms 8588 KB Output is correct
80 Correct 912 ms 8740 KB Output is correct
81 Correct 873 ms 8720 KB Output is correct
82 Correct 949 ms 8388 KB Output is correct
83 Correct 1002 ms 8240 KB Output is correct
84 Correct 989 ms 8416 KB Output is correct
85 Correct 2513 ms 17540 KB Output is correct
86 Correct 236 ms 15200 KB Output is correct
87 Correct 85 ms 7792 KB Output is correct
88 Correct 780 ms 9592 KB Output is correct
89 Correct 2615 ms 16932 KB Output is correct
90 Correct 852 ms 9364 KB Output is correct
91 Correct 2016 ms 11144 KB Output is correct
92 Correct 2041 ms 11068 KB Output is correct
93 Correct 2839 ms 11060 KB Output is correct
94 Correct 2161 ms 14300 KB Output is correct
95 Correct 2192 ms 14408 KB Output is correct
96 Correct 2150 ms 14216 KB Output is correct
97 Correct 456 ms 9528 KB Output is correct
98 Correct 547 ms 9452 KB Output is correct
99 Correct 2580 ms 17124 KB Output is correct
100 Correct 2387 ms 17280 KB Output is correct
101 Correct 2434 ms 17084 KB Output is correct
102 Correct 2446 ms 17096 KB Output is correct
103 Correct 2232 ms 15256 KB Output is correct
104 Correct 2203 ms 15264 KB Output is correct
105 Correct 1592 ms 14784 KB Output is correct
106 Correct 1310 ms 13828 KB Output is correct
107 Correct 1511 ms 15400 KB Output is correct
108 Correct 2355 ms 16504 KB Output is correct
109 Correct 989 ms 8476 KB Output is correct