oj.uz

답안 #523196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523196 2022-02-07T07:45:04 Z LptN21 다리 (APIO19_bridges) C++14
100 / 100
 2687 ms 43544 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
#define FIRSTBIT(x) __builtin_ctzll(x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, int> ii;

/* */
template<class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template<class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
/* */

/* CODE BELOW */
const int N = 5e4 + 7, M = 1e5 + 7;
const int oo = 1e9 + 7;
const int MOD = 1e9 + 7;

int n, m, q, t;

const int B = 825; // size block

struct Edge{
    int u, v, w;
    bool operator<(const Edge &e) const {
        if(w != e.w) return w < e.w;
        if(u != e.u) return u < e.u;
        return v < e.v;
    }
} e[M];

struct Query{int t, u, w;} qry[M];
bool changedEdge[M];
vector<int> careEdge[B + 7];
int ans[M];

//
int dsu[N], vsz[N];
vector<int> rollback;
int root(int u) {
    while(dsu[u] != u) u = dsu[u];
    return u;
}
bool join(int u, int v) {
    if((u=root(u)) == (v=root(v))) return 0;
    if(dsu[u] < dsu[v]) swap(u, v);
    rollback.pb(v);
    vsz[u]+= vsz[v], dsu[v] = u;
    return 1;
}
void goback(int time) {
    while(sz(rollback)>time) {
        int v = rollback.back();
        vsz[dsu[v]]-=vsz[v];
        dsu[v] = v;
        rollback.pop_back();
    }
}
//

void init() {
    iota(dsu+1, dsu+n+1, 1);
    fill(vsz+1, vsz+n+1, 1);
    //rollback.clear();
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d", &n, &m);
    int u, v, w;
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d", &u, &v, &w);
        e[i] = {u, v, w};
    }
    scanf("%d", &q);
    for(int i=1;i<=q;i++) {
        scanf("%d%d%d", &t, &u, &w);
        qry[i] = {t, u, w};
    }

    for(int r, l=1;l<=q;l = r+1) {
        r = min(q, l+B-1); init();
        vector<int> ask, update, unchanged;
        for(int i=l;i<=r;i++) {
            if(qry[i].t == 1) {
                update.pb(i);
                changedEdge[qry[i].u] = 1;
            } else ask.pb(i);
        }

        for(int i=l;i<=r;i++) {
            if(qry[i].t == 1) {
                e[qry[i].u].w = qry[i].w;
            } else {
                careEdge[i-l+1].clear();
                for(int j:update) {
                    if(e[qry[j].u].w>=qry[i].w) {
                        careEdge[i-l+1].pb(qry[j].u);
                    }
                }
            }
        }
        for(int i=1;i<=m;i++) if(!changedEdge[i]) unchanged.pb(i);

        sort(all(ask), [&] (int x, int y) {return qry[x].w > qry[y].w;});
        sort(all(unchanged), [&] (int x, int y) {return e[x].w > e[y].w;});

        int j = 0;
        for(int i:ask) {
            for(;j<sz(unchanged);j++) {
                int k = unchanged[j];
                if(e[k].w>=qry[i].w) join(e[k].u, e[k].v);
                else break;
            }
            int prvSize = sz(rollback);

            for(int k:careEdge[i-l+1]) {
                //printf("%d | %d %d\n", k, e[k].u, e[k].v);
                join(e[k].u, e[k].v);
            }
            ans[i] = vsz[root(qry[i].u)];
            goback(prvSize);
        }

        for(int i:update) changedEdge[qry[i].u] = 0;
    }

    for(int i=1;i<=q;i++) {
        if(qry[i].t == 2) printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%d%d%d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%d%d%d", &t, &u, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 35 ms 2244 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 44 ms 2188 KB Output is correct
6 Correct 28 ms 2064 KB Output is correct
7 Correct 36 ms 2252 KB Output is correct
8 Correct 36 ms 2128 KB Output is correct
9 Correct 39 ms 2112 KB Output is correct
10 Correct 34 ms 2156 KB Output is correct
11 Correct 36 ms 2200 KB Output is correct
12 Correct 53 ms 2240 KB Output is correct
13 Correct 42 ms 2200 KB Output is correct
14 Correct 39 ms 2172 KB Output is correct
15 Correct 41 ms 2200 KB Output is correct
16 Correct 38 ms 2240 KB Output is correct
17 Correct 38 ms 2244 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1445 ms 37892 KB Output is correct
2 Correct 1424 ms 37920 KB Output is correct
3 Correct 1422 ms 37916 KB Output is correct
4 Correct 1453 ms 37952 KB Output is correct
5 Correct 1407 ms 37964 KB Output is correct
6 Correct 2139 ms 37816 KB Output is correct
7 Correct 2129 ms 40256 KB Output is correct
8 Correct 2089 ms 40336 KB Output is correct
9 Correct 38 ms 3364 KB Output is correct
10 Correct 1268 ms 39616 KB Output is correct
11 Correct 1123 ms 39488 KB Output is correct
12 Correct 1318 ms 38948 KB Output is correct
13 Correct 1322 ms 42032 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1214 ms 20892 KB Output is correct
2 Correct 992 ms 7720 KB Output is correct
3 Correct 1667 ms 20752 KB Output is correct
4 Correct 1189 ms 20836 KB Output is correct
5 Correct 41 ms 2064 KB Output is correct
6 Correct 1499 ms 20812 KB Output is correct
7 Correct 1227 ms 20828 KB Output is correct
8 Correct 1078 ms 20872 KB Output is correct
9 Correct 908 ms 19444 KB Output is correct
10 Correct 830 ms 19532 KB Output is correct
11 Correct 985 ms 22576 KB Output is correct
12 Correct 823 ms 22264 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2009 ms 37060 KB Output is correct
2 Correct 39 ms 2032 KB Output is correct
3 Correct 229 ms 2612 KB Output is correct
4 Correct 98 ms 2556 KB Output is correct
5 Correct 1121 ms 37052 KB Output is correct
6 Correct 1983 ms 37044 KB Output is correct
7 Correct 1035 ms 37032 KB Output is correct
8 Correct 1039 ms 35972 KB Output is correct
9 Correct 987 ms 35980 KB Output is correct
10 Correct 1012 ms 36000 KB Output is correct
11 Correct 1533 ms 36616 KB Output is correct
12 Correct 1471 ms 36664 KB Output is correct
13 Correct 1510 ms 36672 KB Output is correct
14 Correct 979 ms 36976 KB Output is correct
15 Correct 1016 ms 36968 KB Output is correct
16 Correct 2084 ms 37060 KB Output is correct
17 Correct 1964 ms 36968 KB Output is correct
18 Correct 1897 ms 37000 KB Output is correct
19 Correct 1963 ms 36964 KB Output is correct
20 Correct 1596 ms 36808 KB Output is correct
21 Correct 1609 ms 36772 KB Output is correct
22 Correct 1932 ms 36880 KB Output is correct
23 Correct 1111 ms 36768 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1445 ms 37892 KB Output is correct
2 Correct 1424 ms 37920 KB Output is correct
3 Correct 1422 ms 37916 KB Output is correct
4 Correct 1453 ms 37952 KB Output is correct
5 Correct 1407 ms 37964 KB Output is correct
6 Correct 2139 ms 37816 KB Output is correct
7 Correct 2129 ms 40256 KB Output is correct
8 Correct 2089 ms 40336 KB Output is correct
9 Correct 38 ms 3364 KB Output is correct
10 Correct 1268 ms 39616 KB Output is correct
11 Correct 1123 ms 39488 KB Output is correct
12 Correct 1318 ms 38948 KB Output is correct
13 Correct 1322 ms 42032 KB Output is correct
14 Correct 1214 ms 20892 KB Output is correct
15 Correct 992 ms 7720 KB Output is correct
16 Correct 1667 ms 20752 KB Output is correct
17 Correct 1189 ms 20836 KB Output is correct
18 Correct 41 ms 2064 KB Output is correct
19 Correct 1499 ms 20812 KB Output is correct
20 Correct 1227 ms 20828 KB Output is correct
21 Correct 1078 ms 20872 KB Output is correct
22 Correct 908 ms 19444 KB Output is correct
23 Correct 830 ms 19532 KB Output is correct
24 Correct 985 ms 22576 KB Output is correct
25 Correct 823 ms 22264 KB Output is correct
26 Correct 1614 ms 40616 KB Output is correct
27 Correct 1869 ms 40324 KB Output is correct
28 Correct 1583 ms 40684 KB Output is correct
29 Correct 1238 ms 40672 KB Output is correct
30 Correct 1684 ms 40512 KB Output is correct
31 Correct 1670 ms 40568 KB Output is correct
32 Correct 1705 ms 40388 KB Output is correct
33 Correct 1472 ms 40716 KB Output is correct
34 Correct 1487 ms 40672 KB Output is correct
35 Correct 1492 ms 40700 KB Output is correct
36 Correct 1218 ms 40796 KB Output is correct
37 Correct 1193 ms 40716 KB Output is correct
38 Correct 1186 ms 40644 KB Output is correct
39 Correct 1069 ms 39240 KB Output is correct
40 Correct 1028 ms 39292 KB Output is correct
41 Correct 1048 ms 39484 KB Output is correct
42 Correct 1010 ms 41476 KB Output is correct
43 Correct 1032 ms 41428 KB Output is correct
44 Correct 1002 ms 41336 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 35 ms 2244 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 44 ms 2188 KB Output is correct
6 Correct 28 ms 2064 KB Output is correct
7 Correct 36 ms 2252 KB Output is correct
8 Correct 36 ms 2128 KB Output is correct
9 Correct 39 ms 2112 KB Output is correct
10 Correct 34 ms 2156 KB Output is correct
11 Correct 36 ms 2200 KB Output is correct
12 Correct 53 ms 2240 KB Output is correct
13 Correct 42 ms 2200 KB Output is correct
14 Correct 39 ms 2172 KB Output is correct
15 Correct 41 ms 2200 KB Output is correct
16 Correct 38 ms 2240 KB Output is correct
17 Correct 38 ms 2244 KB Output is correct
18 Correct 1445 ms 37892 KB Output is correct
19 Correct 1424 ms 37920 KB Output is correct
20 Correct 1422 ms 37916 KB Output is correct
21 Correct 1453 ms 37952 KB Output is correct
22 Correct 1407 ms 37964 KB Output is correct
23 Correct 2139 ms 37816 KB Output is correct
24 Correct 2129 ms 40256 KB Output is correct
25 Correct 2089 ms 40336 KB Output is correct
26 Correct 38 ms 3364 KB Output is correct
27 Correct 1268 ms 39616 KB Output is correct
28 Correct 1123 ms 39488 KB Output is correct
29 Correct 1318 ms 38948 KB Output is correct
30 Correct 1322 ms 42032 KB Output is correct
31 Correct 1214 ms 20892 KB Output is correct
32 Correct 992 ms 7720 KB Output is correct
33 Correct 1667 ms 20752 KB Output is correct
34 Correct 1189 ms 20836 KB Output is correct
35 Correct 41 ms 2064 KB Output is correct
36 Correct 1499 ms 20812 KB Output is correct
37 Correct 1227 ms 20828 KB Output is correct
38 Correct 1078 ms 20872 KB Output is correct
39 Correct 908 ms 19444 KB Output is correct
40 Correct 830 ms 19532 KB Output is correct
41 Correct 985 ms 22576 KB Output is correct
42 Correct 823 ms 22264 KB Output is correct
43 Correct 2009 ms 37060 KB Output is correct
44 Correct 39 ms 2032 KB Output is correct
45 Correct 229 ms 2612 KB Output is correct
46 Correct 98 ms 2556 KB Output is correct
47 Correct 1121 ms 37052 KB Output is correct
48 Correct 1983 ms 37044 KB Output is correct
49 Correct 1035 ms 37032 KB Output is correct
50 Correct 1039 ms 35972 KB Output is correct
51 Correct 987 ms 35980 KB Output is correct
52 Correct 1012 ms 36000 KB Output is correct
53 Correct 1533 ms 36616 KB Output is correct
54 Correct 1471 ms 36664 KB Output is correct
55 Correct 1510 ms 36672 KB Output is correct
56 Correct 979 ms 36976 KB Output is correct
57 Correct 1016 ms 36968 KB Output is correct
58 Correct 2084 ms 37060 KB Output is correct
59 Correct 1964 ms 36968 KB Output is correct
60 Correct 1897 ms 37000 KB Output is correct
61 Correct 1963 ms 36964 KB Output is correct
62 Correct 1596 ms 36808 KB Output is correct
63 Correct 1609 ms 36772 KB Output is correct
64 Correct 1932 ms 36880 KB Output is correct
65 Correct 1111 ms 36768 KB Output is correct
66 Correct 1614 ms 40616 KB Output is correct
67 Correct 1869 ms 40324 KB Output is correct
68 Correct 1583 ms 40684 KB Output is correct
69 Correct 1238 ms 40672 KB Output is correct
70 Correct 1684 ms 40512 KB Output is correct
71 Correct 1670 ms 40568 KB Output is correct
72 Correct 1705 ms 40388 KB Output is correct
73 Correct 1472 ms 40716 KB Output is correct
74 Correct 1487 ms 40672 KB Output is correct
75 Correct 1492 ms 40700 KB Output is correct
76 Correct 1218 ms 40796 KB Output is correct
77 Correct 1193 ms 40716 KB Output is correct
78 Correct 1186 ms 40644 KB Output is correct
79 Correct 1069 ms 39240 KB Output is correct
80 Correct 1028 ms 39292 KB Output is correct
81 Correct 1048 ms 39484 KB Output is correct
82 Correct 1010 ms 41476 KB Output is correct
83 Correct 1032 ms 41428 KB Output is correct
84 Correct 1002 ms 41336 KB Output is correct
85 Correct 2372 ms 42784 KB Output is correct
86 Correct 251 ms 6212 KB Output is correct
87 Correct 134 ms 6276 KB Output is correct
88 Correct 1477 ms 41264 KB Output is correct
89 Correct 2398 ms 42840 KB Output is correct
90 Correct 1526 ms 41156 KB Output is correct
91 Correct 1550 ms 40496 KB Output is correct
92 Correct 1492 ms 40668 KB Output is correct
93 Correct 1924 ms 40340 KB Output is correct
94 Correct 1916 ms 41804 KB Output is correct
95 Correct 1933 ms 41872 KB Output is correct
96 Correct 2233 ms 41480 KB Output is correct
97 Correct 1167 ms 39888 KB Output is correct
98 Correct 1266 ms 42996 KB Output is correct
99 Correct 2433 ms 42660 KB Output is correct
100 Correct 2390 ms 42808 KB Output is correct
101 Correct 2473 ms 42844 KB Output is correct
102 Correct 2431 ms 42812 KB Output is correct
103 Correct 2500 ms 41876 KB Output is correct
104 Correct 2498 ms 41860 KB Output is correct
105 Correct 1933 ms 43544 KB Output is correct
106 Correct 1588 ms 43232 KB Output is correct
107 Correct 1874 ms 40584 KB Output is correct
108 Correct 2687 ms 42220 KB Output is correct
109 Correct 1742 ms 40516 KB Output is correct