oj.uz

답안 #397972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397972 2021-05-03T13:00:04 Z IloveN 다리 (APIO19_bridges) C++14
100 / 100
 1748 ms 172888 KB 
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 1e5 + 10;
const int block = 400;

struct query {int tp, x, y;};
int n, m, q, d[N], mark[N], ans[N], p[N], sz[N];
pii E[N];
query Q[N];
vi ad[N];

bool cmp(int x, int y) { return d[x] > d[y];}
bool cmp2(int x, int y) { return Q[x].y > Q[y].y;}

int find_root(int u) { return p[u] > 0 ? (p[u] = find_root(p[u])) : u;}

void merg(int u, int v)
{
    if (u==v) return;
    if (p[u] > p[v]) swap(u, v);
    if (p[u] == p[v]) --p[u];
    p[v] = u;
    sz[u] += sz[v];
}

vi G[N];
int vis[N], res;

void dfs(int u)
{
    vis[u] = 1;
    res += sz[u];
    for (int v : G[u])
        if (!vis[v]) dfs(v);
}

int main()
{
    //freopen("ss.inp", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> E[i].fi >> E[i].se >> d[i];
    cin >> q;
    for (int i = 1; i <= q; ++i) cin >> Q[i].tp >> Q[i].x >> Q[i].y;
    vi sorted_E;
    for (int i = 1; i <= m; ++i) sorted_E.eb(i);
    sort(all(sorted_E), cmp);
    for (int i = 1; i <= q; ++i) ad[i].reserve(block);
    vi normal_edge;
    normal_edge.reserve(m);
    for (int sta = 1; sta <= q; sta += block)
    {
        int en = min(sta + block - 1, q);
        vi spe_edge, Q2;
        for (int i = sta; i <= en; ++i)
            if (Q[i].tp == 1)
            {
                if (!mark[Q[i].x]) mark[Q[i].x] = 1, spe_edge.eb(Q[i].x);
            }
            else Q2.eb(i);
        for (int i = sta; i <= en; ++i)
            if (Q[i].tp == 1) d[Q[i].x] = Q[i].y;
            else
            {
                for (int x : spe_edge)
                    if (d[x] >= Q[i].y) ad[i].eb(x);
            }
        sort(all(Q2), cmp2);
        normal_edge.clear();
        for (int i : sorted_E)
            if (!mark[i]) normal_edge.eb(i);
            else mark[i] = 0;
        for (int i = 1; i <= n; ++i) p[i] = 0, sz[i] = 1;
        int j = 0;
        for (int id : Q2)
        {
            while (j < (int)normal_edge.size() && d[normal_edge[j]] >= Q[id].y)
            {
                pii pa = E[normal_edge[j]];
                merg(find_root(pa.fi), find_root(pa.se));
                ++j;
            }
            stack<int> st;
            for (int i : ad[id])
            {
                int u = find_root(E[i].fi);
                int v = find_root(E[i].se);
                if (u != v)
                {
                    G[u].eb(v);
                    G[v].eb(u);
                    st.push(u);
                    st.push(v);
                }
            }
            res = 0;
            dfs(find_root(Q[id].x));
            vis[find_root(Q[id].x)] = 0;
            ans[id] = res;
            while (!st.empty()) G[st.top()].clear(), vis[st.top()] = 0, st.pop();
        }
        sort(all(spe_edge), cmp);
        merge(all(normal_edge), all(spe_edge), sorted_E.begin(), cmp);
    }
    for (int i = 1; i <= q; ++i)
        if (Q[i].tp == 2) cout << ans[i] << "\n";
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5124 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 27 ms 21032 KB Output is correct
4 Correct 16 ms 21172 KB Output is correct
5 Correct 27 ms 21168 KB Output is correct
6 Correct 25 ms 21196 KB Output is correct
7 Correct 28 ms 21068 KB Output is correct
8 Correct 27 ms 21152 KB Output is correct
9 Correct 43 ms 21076 KB Output is correct
10 Correct 28 ms 21068 KB Output is correct
11 Correct 26 ms 21196 KB Output is correct
12 Correct 29 ms 21132 KB Output is correct
13 Correct 33 ms 21132 KB Output is correct
14 Correct 34 ms 21164 KB Output is correct
15 Correct 29 ms 21196 KB Output is correct
16 Correct 36 ms 21084 KB Output is correct
17 Correct 31 ms 21060 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1159 ms 167916 KB Output is correct
2 Correct 1201 ms 170748 KB Output is correct
3 Correct 1178 ms 170564 KB Output is correct
4 Correct 1198 ms 170700 KB Output is correct
5 Correct 1155 ms 170752 KB Output is correct
6 Correct 1614 ms 169580 KB Output is correct
7 Correct 1476 ms 169712 KB Output is correct
8 Correct 1451 ms 169704 KB Output is correct
9 Correct 131 ms 166212 KB Output is correct
10 Correct 1256 ms 169316 KB Output is correct
11 Correct 1141 ms 169568 KB Output is correct
12 Correct 974 ms 169556 KB Output is correct
13 Correct 1000 ms 169840 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 914 ms 166852 KB Output is correct
2 Correct 701 ms 166956 KB Output is correct
3 Correct 1056 ms 169096 KB Output is correct
4 Correct 881 ms 169256 KB Output is correct
5 Correct 133 ms 166212 KB Output is correct
6 Correct 973 ms 169128 KB Output is correct
7 Correct 819 ms 169180 KB Output is correct
8 Correct 724 ms 169124 KB Output is correct
9 Correct 648 ms 168840 KB Output is correct
10 Correct 606 ms 168712 KB Output is correct
11 Correct 667 ms 169324 KB Output is correct
12 Correct 597 ms 169216 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1329 ms 167688 KB Output is correct
2 Correct 129 ms 164804 KB Output is correct
3 Correct 130 ms 22968 KB Output is correct
4 Correct 101 ms 22980 KB Output is correct
5 Correct 1061 ms 167744 KB Output is correct
6 Correct 1272 ms 167636 KB Output is correct
7 Correct 1111 ms 167752 KB Output is correct
8 Correct 775 ms 166576 KB Output is correct
9 Correct 759 ms 166500 KB Output is correct
10 Correct 788 ms 166728 KB Output is correct
11 Correct 1310 ms 167112 KB Output is correct
12 Correct 1212 ms 167012 KB Output is correct
13 Correct 1240 ms 167312 KB Output is correct
14 Correct 983 ms 167784 KB Output is correct
15 Correct 1014 ms 167828 KB Output is correct
16 Correct 1475 ms 167812 KB Output is correct
17 Correct 1470 ms 167736 KB Output is correct
18 Correct 1447 ms 167852 KB Output is correct
19 Correct 1471 ms 167744 KB Output is correct
20 Correct 1388 ms 167408 KB Output is correct
21 Correct 1396 ms 167616 KB Output is correct
22 Correct 1407 ms 167804 KB Output is correct
23 Correct 1195 ms 167552 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1159 ms 167916 KB Output is correct
2 Correct 1201 ms 170748 KB Output is correct
3 Correct 1178 ms 170564 KB Output is correct
4 Correct 1198 ms 170700 KB Output is correct
5 Correct 1155 ms 170752 KB Output is correct
6 Correct 1614 ms 169580 KB Output is correct
7 Correct 1476 ms 169712 KB Output is correct
8 Correct 1451 ms 169704 KB Output is correct
9 Correct 131 ms 166212 KB Output is correct
10 Correct 1256 ms 169316 KB Output is correct
11 Correct 1141 ms 169568 KB Output is correct
12 Correct 974 ms 169556 KB Output is correct
13 Correct 1000 ms 169840 KB Output is correct
14 Correct 914 ms 166852 KB Output is correct
15 Correct 701 ms 166956 KB Output is correct
16 Correct 1056 ms 169096 KB Output is correct
17 Correct 881 ms 169256 KB Output is correct
18 Correct 133 ms 166212 KB Output is correct
19 Correct 973 ms 169128 KB Output is correct
20 Correct 819 ms 169180 KB Output is correct
21 Correct 724 ms 169124 KB Output is correct
22 Correct 648 ms 168840 KB Output is correct
23 Correct 606 ms 168712 KB Output is correct
24 Correct 667 ms 169324 KB Output is correct
25 Correct 597 ms 169216 KB Output is correct
26 Correct 1118 ms 170544 KB Output is correct
27 Correct 1413 ms 170544 KB Output is correct
28 Correct 1261 ms 170728 KB Output is correct
29 Correct 963 ms 170548 KB Output is correct
30 Correct 1388 ms 170400 KB Output is correct
31 Correct 1367 ms 170560 KB Output is correct
32 Correct 1391 ms 170660 KB Output is correct
33 Correct 1198 ms 170712 KB Output is correct
34 Correct 1206 ms 170688 KB Output is correct
35 Correct 1250 ms 170580 KB Output is correct
36 Correct 997 ms 170488 KB Output is correct
37 Correct 973 ms 170440 KB Output is correct
38 Correct 980 ms 170476 KB Output is correct
39 Correct 889 ms 169988 KB Output is correct
40 Correct 840 ms 169852 KB Output is correct
41 Correct 853 ms 169928 KB Output is correct
42 Correct 788 ms 170576 KB Output is correct
43 Correct 813 ms 170600 KB Output is correct
44 Correct 801 ms 170764 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5124 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 27 ms 21032 KB Output is correct
4 Correct 16 ms 21172 KB Output is correct
5 Correct 27 ms 21168 KB Output is correct
6 Correct 25 ms 21196 KB Output is correct
7 Correct 28 ms 21068 KB Output is correct
8 Correct 27 ms 21152 KB Output is correct
9 Correct 43 ms 21076 KB Output is correct
10 Correct 28 ms 21068 KB Output is correct
11 Correct 26 ms 21196 KB Output is correct
12 Correct 29 ms 21132 KB Output is correct
13 Correct 33 ms 21132 KB Output is correct
14 Correct 34 ms 21164 KB Output is correct
15 Correct 29 ms 21196 KB Output is correct
16 Correct 36 ms 21084 KB Output is correct
17 Correct 31 ms 21060 KB Output is correct
18 Correct 1159 ms 167916 KB Output is correct
19 Correct 1201 ms 170748 KB Output is correct
20 Correct 1178 ms 170564 KB Output is correct
21 Correct 1198 ms 170700 KB Output is correct
22 Correct 1155 ms 170752 KB Output is correct
23 Correct 1614 ms 169580 KB Output is correct
24 Correct 1476 ms 169712 KB Output is correct
25 Correct 1451 ms 169704 KB Output is correct
26 Correct 131 ms 166212 KB Output is correct
27 Correct 1256 ms 169316 KB Output is correct
28 Correct 1141 ms 169568 KB Output is correct
29 Correct 974 ms 169556 KB Output is correct
30 Correct 1000 ms 169840 KB Output is correct
31 Correct 914 ms 166852 KB Output is correct
32 Correct 701 ms 166956 KB Output is correct
33 Correct 1056 ms 169096 KB Output is correct
34 Correct 881 ms 169256 KB Output is correct
35 Correct 133 ms 166212 KB Output is correct
36 Correct 973 ms 169128 KB Output is correct
37 Correct 819 ms 169180 KB Output is correct
38 Correct 724 ms 169124 KB Output is correct
39 Correct 648 ms 168840 KB Output is correct
40 Correct 606 ms 168712 KB Output is correct
41 Correct 667 ms 169324 KB Output is correct
42 Correct 597 ms 169216 KB Output is correct
43 Correct 1329 ms 167688 KB Output is correct
44 Correct 129 ms 164804 KB Output is correct
45 Correct 130 ms 22968 KB Output is correct
46 Correct 101 ms 22980 KB Output is correct
47 Correct 1061 ms 167744 KB Output is correct
48 Correct 1272 ms 167636 KB Output is correct
49 Correct 1111 ms 167752 KB Output is correct
50 Correct 775 ms 166576 KB Output is correct
51 Correct 759 ms 166500 KB Output is correct
52 Correct 788 ms 166728 KB Output is correct
53 Correct 1310 ms 167112 KB Output is correct
54 Correct 1212 ms 167012 KB Output is correct
55 Correct 1240 ms 167312 KB Output is correct
56 Correct 983 ms 167784 KB Output is correct
57 Correct 1014 ms 167828 KB Output is correct
58 Correct 1475 ms 167812 KB Output is correct
59 Correct 1470 ms 167736 KB Output is correct
60 Correct 1447 ms 167852 KB Output is correct
61 Correct 1471 ms 167744 KB Output is correct
62 Correct 1388 ms 167408 KB Output is correct
63 Correct 1396 ms 167616 KB Output is correct
64 Correct 1407 ms 167804 KB Output is correct
65 Correct 1195 ms 167552 KB Output is correct
66 Correct 1118 ms 170544 KB Output is correct
67 Correct 1413 ms 170544 KB Output is correct
68 Correct 1261 ms 170728 KB Output is correct
69 Correct 963 ms 170548 KB Output is correct
70 Correct 1388 ms 170400 KB Output is correct
71 Correct 1367 ms 170560 KB Output is correct
72 Correct 1391 ms 170660 KB Output is correct
73 Correct 1198 ms 170712 KB Output is correct
74 Correct 1206 ms 170688 KB Output is correct
75 Correct 1250 ms 170580 KB Output is correct
76 Correct 997 ms 170488 KB Output is correct
77 Correct 973 ms 170440 KB Output is correct
78 Correct 980 ms 170476 KB Output is correct
79 Correct 889 ms 169988 KB Output is correct
80 Correct 840 ms 169852 KB Output is correct
81 Correct 853 ms 169928 KB Output is correct
82 Correct 788 ms 170576 KB Output is correct
83 Correct 813 ms 170600 KB Output is correct
84 Correct 801 ms 170764 KB Output is correct
85 Correct 1599 ms 172724 KB Output is correct
86 Correct 142 ms 25152 KB Output is correct
87 Correct 112 ms 25452 KB Output is correct
88 Correct 1375 ms 170968 KB Output is correct
89 Correct 1598 ms 172888 KB Output is correct
90 Correct 1345 ms 170808 KB Output is correct
91 Correct 1224 ms 170568 KB Output is correct
92 Correct 1200 ms 170728 KB Output is correct
93 Correct 1444 ms 169736 KB Output is correct
94 Correct 1529 ms 171592 KB Output is correct
95 Correct 1520 ms 171736 KB Output is correct
96 Correct 1485 ms 170472 KB Output is correct
97 Correct 1195 ms 170560 KB Output is correct
98 Correct 1245 ms 170504 KB Output is correct
99 Correct 1733 ms 172752 KB Output is correct
100 Correct 1712 ms 172604 KB Output is correct
101 Correct 1709 ms 172820 KB Output is correct
102 Correct 1748 ms 172740 KB Output is correct
103 Correct 1607 ms 170676 KB Output is correct
104 Correct 1649 ms 170948 KB Output is correct
105 Correct 1478 ms 170496 KB Output is correct
106 Correct 1285 ms 170212 KB Output is correct
107 Correct 1526 ms 170920 KB Output is correct
108 Correct 1671 ms 171624 KB Output is correct
109 Correct 1419 ms 169496 KB Output is correct