oj.uz

Submission #728596

# Submission time Handle Problem Language Result Execution time Memory
728596 2023-04-22T16:49:19 Z Username4132 Bridges (APIO19_bridges) C++14
100 / 100
 1714 ms 12260 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

struct query{
    int ind, ve, weight;
    query(int Ind, int Ve, int Weight) : ind(Ind), ve(Ve), weight(Weight){}
    query(){}
};

struct reversibleChange{
    int ind, sind, par, sz;
    reversibleChange(int Ind, int Sind, int Par, int Sz) : ind(Ind), sind(Sind), par(Par), sz(Sz){};
};

const int MAXN=50010, MAXE=100010;
int n, m, q, lastLeft[MAXE], lastFull[MAXE], lastSeen[MAXE], lastWeight[MAXE], par[MAXN], size[MAXN];
bool seen[MAXE], notodo[MAXE];
pii edges[MAXE];
vector<query> upd, ask, done;
vector<pii> ans;
vector<reversibleChange> changes;

auto cmp = [](query a, query b){
    return a.weight>b.weight;
};


int root(int a){
    while(par[a]!=a) a=par[a];
    return a;
}

void combine(int edgeInd, bool save){
    int a=edges[edgeInd].F, b=edges[edgeInd].S;
    int root_a=root(a), root_b=root(b);
    if(root_a==root_b) return;
    if(size[root_a]<size[root_b]) swap(root_a, root_b);

    if(!save) changes.PB(reversibleChange(root_a, root_b, par[root_b], size[root_a]));
    size[root_a]+=size[root_b];
    par[root_b]=root_a;
}

void rollback(){
    while(!changes.empty()){
        reversibleChange ch = changes.back();
        changes.pop_back();
        par[ch.sind]=ch.par;
        size[ch.ind]=ch.sz;
    }
}

void reset(){
    changes.clear();
    forn(i, n) par[i]=i, size[i]=1;
}


int main(){
    forn(i, MAXE) lastSeen[i]=-2;
    done.reserve(MAXE);
    scanf("%d %d", &n , &m);
    forn(i, m){
        int a, b, c; scanf("%d %d %d", &a, &b, &c); --a, --b;
        edges[i]={a, b};
        done.PB(query(i, i, c));
        lastWeight[i]=c;
    }
    upd.PB(query(-1, 0, lastWeight[0]));
    sort(done.begin(), done.end(), cmp);
    scanf("%d", &q);
    forn(i, q){
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        if(a==1) upd.PB(query(i+m, b-1, c));
        else ask.PB(query(i+m, b-1, c));
    }
    int qnum=upd.size(), sq=0, answered=0;

    while((sq+1)*(sq+1)<=qnum) ++sq;
    for(int l=0; l<qnum && answered<(int)ask.size(); l+=sq){
        reset();
        int r=min(l+sq, qnum);
        int bnd=(r==qnum? 1000000 : upd[r].ind);
        int lstQ=answered, updated=0;
        forsn(i, l, r) seen[upd[i].ve]=true;
        
        while(lstQ<(int)ask.size() && ask[lstQ].ind<bnd) ++lstQ;
        sort(ask.begin()+answered, ask.begin()+lstQ, cmp);
        forsn(i, answered, lstQ){
            query question = ask[i];
            while(updated<(int)done.size() && done[updated].weight>=question.weight){
                if(!seen[done[updated].ve]) combine(done[updated].ve, true);
                updated++;
            }
            forsn(j, l, r){
                if(upd[j].ind>question.ind) break;
                lastSeen[upd[j].ve]=j;
                notodo[upd[j].ve]=true;
            }
            forsn(j, l, r){
                if(lastSeen[upd[j].ve]==j && upd[j].weight>=question.weight) combine(upd[j].ve, false);
                else if(!notodo[upd[j].ve] && (lastWeight[upd[j].ve]>=question.weight)) combine(upd[j].ve, false);
            }
            int ret = size[root(question.ve)];
            ans.PB({question.ind, ret});
            forsn(j, l, r) notodo[upd[j].ve]=false, lastSeen[upd[j].ve]=-2;
            rollback();
        }
        answered=lstQ;
        vector<query> le, ri;
        forsn(i, l, r) lastSeen[upd[i].ve]=i;
        forn(i, done.size()) if(!seen[done[i].ve]) le.PB(done[i]);
        forsn(i, l, r) if(lastSeen[upd[i].ve]==i) ri.PB(upd[i]), lastWeight[upd[i].ve]=upd[i].weight;
        sort(ri.begin(), ri.end(), cmp);
        done.resize(le.size()+ri.size());
        merge(le.begin(), le.end(), ri.begin(), ri.end(), done.begin(), cmp);
        forsn(i, l, r) seen[upd[i].ve]=false;
    }

    sort(ans.begin(), ans.end());
    for(auto pr:ans) printf("%d\n", pr.S);
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d", &n , &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:72:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         int a, b, c; scanf("%d %d %d", &a, &b, &c); --a, --b;
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:81:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         int a, b, c; scanf("%d %d %d", &a, &b, &c);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 13 ms 1196 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 13 ms 1184 KB Output is correct
6 Correct 10 ms 1128 KB Output is correct
7 Correct 12 ms 1120 KB Output is correct
8 Correct 12 ms 1120 KB Output is correct
9 Correct 12 ms 1052 KB Output is correct
10 Correct 12 ms 1140 KB Output is correct
11 Correct 12 ms 1108 KB Output is correct
12 Correct 13 ms 1148 KB Output is correct
13 Correct 13 ms 1164 KB Output is correct
14 Correct 14 ms 1140 KB Output is correct
15 Correct 14 ms 1108 KB Output is correct
16 Correct 12 ms 1076 KB Output is correct
17 Correct 12 ms 1088 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 8388 KB Output is correct
2 Correct 954 ms 8392 KB Output is correct
3 Correct 956 ms 8304 KB Output is correct
4 Correct 948 ms 8372 KB Output is correct
5 Correct 949 ms 8380 KB Output is correct
6 Correct 1234 ms 8364 KB Output is correct
7 Correct 1189 ms 8380 KB Output is correct
8 Correct 1179 ms 8396 KB Output is correct
9 Correct 60 ms 5196 KB Output is correct
10 Correct 870 ms 7364 KB Output is correct
11 Correct 823 ms 7308 KB Output is correct
12 Correct 767 ms 9060 KB Output is correct
13 Correct 954 ms 7888 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 6788 KB Output is correct
2 Correct 454 ms 4812 KB Output is correct
3 Correct 778 ms 6724 KB Output is correct
4 Correct 683 ms 6992 KB Output is correct
5 Correct 52 ms 5180 KB Output is correct
6 Correct 730 ms 6804 KB Output is correct
7 Correct 659 ms 6960 KB Output is correct
8 Correct 621 ms 6716 KB Output is correct
9 Correct 454 ms 7712 KB Output is correct
10 Correct 404 ms 7776 KB Output is correct
11 Correct 547 ms 6264 KB Output is correct
12 Correct 491 ms 6268 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 11540 KB Output is correct
2 Correct 54 ms 5184 KB Output is correct
3 Correct 51 ms 6700 KB Output is correct
4 Correct 39 ms 6828 KB Output is correct
5 Correct 77 ms 9944 KB Output is correct
6 Correct 104 ms 11528 KB Output is correct
7 Correct 96 ms 9888 KB Output is correct
8 Correct 84 ms 8380 KB Output is correct
9 Correct 80 ms 8316 KB Output is correct
10 Correct 89 ms 8016 KB Output is correct
11 Correct 98 ms 10244 KB Output is correct
12 Correct 91 ms 10408 KB Output is correct
13 Correct 89 ms 10076 KB Output is correct
14 Correct 81 ms 9956 KB Output is correct
15 Correct 88 ms 9912 KB Output is correct
16 Correct 109 ms 11348 KB Output is correct
17 Correct 115 ms 11388 KB Output is correct
18 Correct 115 ms 11528 KB Output is correct
19 Correct 105 ms 11456 KB Output is correct
20 Correct 101 ms 10452 KB Output is correct
21 Correct 106 ms 10424 KB Output is correct
22 Correct 97 ms 11088 KB Output is correct
23 Correct 80 ms 9284 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 8388 KB Output is correct
2 Correct 954 ms 8392 KB Output is correct
3 Correct 956 ms 8304 KB Output is correct
4 Correct 948 ms 8372 KB Output is correct
5 Correct 949 ms 8380 KB Output is correct
6 Correct 1234 ms 8364 KB Output is correct
7 Correct 1189 ms 8380 KB Output is correct
8 Correct 1179 ms 8396 KB Output is correct
9 Correct 60 ms 5196 KB Output is correct
10 Correct 870 ms 7364 KB Output is correct
11 Correct 823 ms 7308 KB Output is correct
12 Correct 767 ms 9060 KB Output is correct
13 Correct 954 ms 7888 KB Output is correct
14 Correct 669 ms 6788 KB Output is correct
15 Correct 454 ms 4812 KB Output is correct
16 Correct 778 ms 6724 KB Output is correct
17 Correct 683 ms 6992 KB Output is correct
18 Correct 52 ms 5180 KB Output is correct
19 Correct 730 ms 6804 KB Output is correct
20 Correct 659 ms 6960 KB Output is correct
21 Correct 621 ms 6716 KB Output is correct
22 Correct 454 ms 7712 KB Output is correct
23 Correct 404 ms 7776 KB Output is correct
24 Correct 547 ms 6264 KB Output is correct
25 Correct 491 ms 6268 KB Output is correct
26 Correct 929 ms 8412 KB Output is correct
27 Correct 1132 ms 8244 KB Output is correct
28 Correct 978 ms 8528 KB Output is correct
29 Correct 840 ms 8384 KB Output is correct
30 Correct 1089 ms 8352 KB Output is correct
31 Correct 1071 ms 8424 KB Output is correct
32 Correct 1109 ms 8416 KB Output is correct
33 Correct 983 ms 8360 KB Output is correct
34 Correct 1016 ms 8600 KB Output is correct
35 Correct 1002 ms 8472 KB Output is correct
36 Correct 831 ms 8344 KB Output is correct
37 Correct 838 ms 8336 KB Output is correct
38 Correct 842 ms 8448 KB Output is correct
39 Correct 490 ms 9104 KB Output is correct
40 Correct 441 ms 9096 KB Output is correct
41 Correct 467 ms 9128 KB Output is correct
42 Correct 863 ms 8128 KB Output is correct
43 Correct 883 ms 7912 KB Output is correct
44 Correct 877 ms 7840 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 13 ms 1196 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 13 ms 1184 KB Output is correct
6 Correct 10 ms 1128 KB Output is correct
7 Correct 12 ms 1120 KB Output is correct
8 Correct 12 ms 1120 KB Output is correct
9 Correct 12 ms 1052 KB Output is correct
10 Correct 12 ms 1140 KB Output is correct
11 Correct 12 ms 1108 KB Output is correct
12 Correct 13 ms 1148 KB Output is correct
13 Correct 13 ms 1164 KB Output is correct
14 Correct 14 ms 1140 KB Output is correct
15 Correct 14 ms 1108 KB Output is correct
16 Correct 12 ms 1076 KB Output is correct
17 Correct 12 ms 1088 KB Output is correct
18 Correct 960 ms 8388 KB Output is correct
19 Correct 954 ms 8392 KB Output is correct
20 Correct 956 ms 8304 KB Output is correct
21 Correct 948 ms 8372 KB Output is correct
22 Correct 949 ms 8380 KB Output is correct
23 Correct 1234 ms 8364 KB Output is correct
24 Correct 1189 ms 8380 KB Output is correct
25 Correct 1179 ms 8396 KB Output is correct
26 Correct 60 ms 5196 KB Output is correct
27 Correct 870 ms 7364 KB Output is correct
28 Correct 823 ms 7308 KB Output is correct
29 Correct 767 ms 9060 KB Output is correct
30 Correct 954 ms 7888 KB Output is correct
31 Correct 669 ms 6788 KB Output is correct
32 Correct 454 ms 4812 KB Output is correct
33 Correct 778 ms 6724 KB Output is correct
34 Correct 683 ms 6992 KB Output is correct
35 Correct 52 ms 5180 KB Output is correct
36 Correct 730 ms 6804 KB Output is correct
37 Correct 659 ms 6960 KB Output is correct
38 Correct 621 ms 6716 KB Output is correct
39 Correct 454 ms 7712 KB Output is correct
40 Correct 404 ms 7776 KB Output is correct
41 Correct 547 ms 6264 KB Output is correct
42 Correct 491 ms 6268 KB Output is correct
43 Correct 102 ms 11540 KB Output is correct
44 Correct 54 ms 5184 KB Output is correct
45 Correct 51 ms 6700 KB Output is correct
46 Correct 39 ms 6828 KB Output is correct
47 Correct 77 ms 9944 KB Output is correct
48 Correct 104 ms 11528 KB Output is correct
49 Correct 96 ms 9888 KB Output is correct
50 Correct 84 ms 8380 KB Output is correct
51 Correct 80 ms 8316 KB Output is correct
52 Correct 89 ms 8016 KB Output is correct
53 Correct 98 ms 10244 KB Output is correct
54 Correct 91 ms 10408 KB Output is correct
55 Correct 89 ms 10076 KB Output is correct
56 Correct 81 ms 9956 KB Output is correct
57 Correct 88 ms 9912 KB Output is correct
58 Correct 109 ms 11348 KB Output is correct
59 Correct 115 ms 11388 KB Output is correct
60 Correct 115 ms 11528 KB Output is correct
61 Correct 105 ms 11456 KB Output is correct
62 Correct 101 ms 10452 KB Output is correct
63 Correct 106 ms 10424 KB Output is correct
64 Correct 97 ms 11088 KB Output is correct
65 Correct 80 ms 9284 KB Output is correct
66 Correct 929 ms 8412 KB Output is correct
67 Correct 1132 ms 8244 KB Output is correct
68 Correct 978 ms 8528 KB Output is correct
69 Correct 840 ms 8384 KB Output is correct
70 Correct 1089 ms 8352 KB Output is correct
71 Correct 1071 ms 8424 KB Output is correct
72 Correct 1109 ms 8416 KB Output is correct
73 Correct 983 ms 8360 KB Output is correct
74 Correct 1016 ms 8600 KB Output is correct
75 Correct 1002 ms 8472 KB Output is correct
76 Correct 831 ms 8344 KB Output is correct
77 Correct 838 ms 8336 KB Output is correct
78 Correct 842 ms 8448 KB Output is correct
79 Correct 490 ms 9104 KB Output is correct
80 Correct 441 ms 9096 KB Output is correct
81 Correct 467 ms 9128 KB Output is correct
82 Correct 863 ms 8128 KB Output is correct
83 Correct 883 ms 7912 KB Output is correct
84 Correct 877 ms 7840 KB Output is correct
85 Correct 1705 ms 12136 KB Output is correct
86 Correct 406 ms 8084 KB Output is correct
87 Correct 301 ms 8164 KB Output is correct
88 Correct 1382 ms 10668 KB Output is correct
89 Correct 1497 ms 12244 KB Output is correct
90 Correct 1392 ms 10580 KB Output is correct
91 Correct 974 ms 8352 KB Output is correct
92 Correct 959 ms 8424 KB Output is correct
93 Correct 1212 ms 8360 KB Output is correct
94 Correct 1344 ms 10440 KB Output is correct
95 Correct 1302 ms 10660 KB Output is correct
96 Correct 1374 ms 10472 KB Output is correct
97 Correct 672 ms 11536 KB Output is correct
98 Correct 1714 ms 9948 KB Output is correct
99 Correct 1571 ms 12056 KB Output is correct
100 Correct 1608 ms 11992 KB Output is correct
101 Correct 1568 ms 12260 KB Output is correct
102 Correct 1619 ms 12176 KB Output is correct
103 Correct 1541 ms 11064 KB Output is correct
104 Correct 1591 ms 10940 KB Output is correct
105 Correct 1677 ms 10436 KB Output is correct
106 Correct 1560 ms 10212 KB Output is correct
107 Correct 806 ms 12024 KB Output is correct
108 Correct 1472 ms 11820 KB Output is correct
109 Correct 1328 ms 9716 KB Output is correct