oj.uz

답안 #521831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521831 2022-02-03T09:20:10 Z XEMPLI5 다리 (APIO19_bridges) C++17
100 / 100
 2089 ms 154088 KB 
#include <bits/stdc++.h>
using namespace std;

#define gc getchar_unlocked
#define fo(i, n) for (int i = 0; i < n; i++)
#define rfo(i, n) for (int i = n - 1; i >= 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define si(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define ss(s) scanf("%s", s)
#define pi(x) printf("%d\n", x)
#define pl(x) printf("%lld\n", x)
#define ps(s) printf("%s\n", s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626

typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

int mpow(int base, int exp);
void dfs(int u, int par);

const int mod = 1'000'000'007;
const int N = 1e5 + 10, M = N;

vi g[N];
int a[N], ans[N], par[N], sz[N];
int n = 0;

stack<int> stck;
void reset()
{
    fo(i, n)
    {
        par[i] = i;
        sz[i] = 1;
    }
}

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

void onion(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    if (sz[a] > sz[b])
        swap(a, b);
    stck.push(a);
    sz[b] += sz[a];
    par[a] = par[b];
}

void rollback(int siz)
{
    while (stck.size() > siz)
    {
        int k = stck.top();
        stck.pop();
        sz[par[k]] -= sz[k];
        par[k] = k;
    }
}

int u[N], v[N], d[N], b[N], r[N], s[N], w[N], ty[N], changed[N];
vi tojoin[N];
const int bs = 1000;

void solve()
{
    int m, q;
    cin >> n >> m;
    fo(i, m)
    {
        cin >> u[i] >> v[i] >> d[i];
        u[i]--;
        v[i]--;
    }
    cin >> q;
    fo(i, q)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            cin >> b[i] >> r[i];
            b[i]--;
            ty[i] = 1;
        }
        else
        {
            cin >> s[i] >> w[i];
            s[i]--;
            ty[i] = 2;
        }
    }
    for (int j = 0; j < q; j += bs)
    {
        reset();
        vi ask, update, nochange;
        fo(i, m) changed[i] = false;
        for (int i = j; i < min(j + bs, q); i++)
        {
            if (ty[i] == 1)
            {
                changed[b[i]] = true;
                update.pb(i);
            }
            else
            {
                ask.pb(i);
            }
        }
        fo(k, m) if (!changed[k]) nochange.pb(k);
        for (int i = j; i < min(j + bs, q); i++)
        {
            if (ty[i] == 1)
            {
                d[b[i]] = r[i];
            }
            else
            {
                tojoin[i].clear();
                for (auto e : update)
                    if (d[b[e]] >= w[i])
                        tojoin[i].pb(b[e]);
            }
        }
        sort(all(ask), [&](int a, int b)
             { return w[a] > w[b]; });
        sort(all(nochange), [&](int a, int b)
             { return d[a] > d[b]; });
        int ptr = 0;
        for (auto e : ask)
        {
            while (ptr < nochange.size() && d[nochange[ptr]] >= w[e])
            {
                onion(u[nochange[ptr]], v[nochange[ptr]]);
                ptr++;
            }
            int prv = stck.size();
            for (auto f : tojoin[e])
                onion(u[f], v[f]);
            ans[e] = sz[find(s[e])];
            rollback(prv);
        }
    }
    fo(i, q) if (ty[i] == 2) cout << ans[i] << '\n';
    return;
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t = 1;
    int cs = 0;
    while (t - cs)
    {
        solve();
        cs++;
    }

    return 0;
}

int mpow(int base, int exp)
{
    base %= mod;
    int result = 1;
    while (exp > 0)
    {
        if (exp & 1)
            result = ((ll)result * base) % mod;
        base = ((ll)base * base) % mod;
        exp >>= 1;
    }
    return result;
}

void ipgraph(int n, int m)
{
    int u, v;
    while (m--)
    {
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }
}

void dfs(int u, int par)
{
    for (int v : g[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
    }
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:82:24: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |     while (stck.size() > siz)
      |            ~~~~~~~~~~~~^~~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:162:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             while (ptr < nochange.size() && d[nochange[ptr]] >= w[e])
      |                    ~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 43 ms 11888 KB Output is correct
4 Correct 6 ms 5196 KB Output is correct
5 Correct 41 ms 12696 KB Output is correct
6 Correct 32 ms 12860 KB Output is correct
7 Correct 36 ms 12948 KB Output is correct
8 Correct 39 ms 11332 KB Output is correct
9 Correct 51 ms 17176 KB Output is correct
10 Correct 45 ms 12096 KB Output is correct
11 Correct 41 ms 11940 KB Output is correct
12 Correct 53 ms 14348 KB Output is correct
13 Correct 47 ms 12484 KB Output is correct
14 Correct 44 ms 11696 KB Output is correct
15 Correct 50 ms 12536 KB Output is correct
16 Correct 44 ms 15456 KB Output is correct
17 Correct 47 ms 14536 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1265 ms 96208 KB Output is correct
2 Correct 1252 ms 96148 KB Output is correct
3 Correct 1265 ms 96300 KB Output is correct
4 Correct 1310 ms 95784 KB Output is correct
5 Correct 1307 ms 96448 KB Output is correct
6 Correct 1912 ms 154088 KB Output is correct
7 Correct 1885 ms 150772 KB Output is correct
8 Correct 1895 ms 150416 KB Output is correct
9 Correct 33 ms 6724 KB Output is correct
10 Correct 1094 ms 121932 KB Output is correct
11 Correct 1006 ms 121016 KB Output is correct
12 Correct 1092 ms 76136 KB Output is correct
13 Correct 1078 ms 69052 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1062 ms 89012 KB Output is correct
2 Correct 851 ms 104004 KB Output is correct
3 Correct 1300 ms 116940 KB Output is correct
4 Correct 1048 ms 88520 KB Output is correct
5 Correct 33 ms 6788 KB Output is correct
6 Correct 1217 ms 108244 KB Output is correct
7 Correct 956 ms 80448 KB Output is correct
8 Correct 826 ms 64712 KB Output is correct
9 Correct 694 ms 56644 KB Output is correct
10 Correct 617 ms 44996 KB Output is correct
11 Correct 700 ms 53820 KB Output is correct
12 Correct 629 ms 43528 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1380 ms 29916 KB Output is correct
2 Correct 35 ms 8132 KB Output is correct
3 Correct 147 ms 9500 KB Output is correct
4 Correct 76 ms 9620 KB Output is correct
5 Correct 710 ms 32272 KB Output is correct
6 Correct 1350 ms 33908 KB Output is correct
7 Correct 685 ms 32172 KB Output is correct
8 Correct 664 ms 31460 KB Output is correct
9 Correct 656 ms 31460 KB Output is correct
10 Correct 653 ms 31428 KB Output is correct
11 Correct 1014 ms 32912 KB Output is correct
12 Correct 1010 ms 32940 KB Output is correct
13 Correct 1055 ms 32876 KB Output is correct
14 Correct 639 ms 32152 KB Output is correct
15 Correct 660 ms 32096 KB Output is correct
16 Correct 1380 ms 33856 KB Output is correct
17 Correct 1379 ms 33788 KB Output is correct
18 Correct 1378 ms 34196 KB Output is correct
19 Correct 1399 ms 34100 KB Output is correct
20 Correct 1150 ms 33180 KB Output is correct
21 Correct 1167 ms 33220 KB Output is correct
22 Correct 1310 ms 33536 KB Output is correct
23 Correct 763 ms 29796 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1265 ms 96208 KB Output is correct
2 Correct 1252 ms 96148 KB Output is correct
3 Correct 1265 ms 96300 KB Output is correct
4 Correct 1310 ms 95784 KB Output is correct
5 Correct 1307 ms 96448 KB Output is correct
6 Correct 1912 ms 154088 KB Output is correct
7 Correct 1885 ms 150772 KB Output is correct
8 Correct 1895 ms 150416 KB Output is correct
9 Correct 33 ms 6724 KB Output is correct
10 Correct 1094 ms 121932 KB Output is correct
11 Correct 1006 ms 121016 KB Output is correct
12 Correct 1092 ms 76136 KB Output is correct
13 Correct 1078 ms 69052 KB Output is correct
14 Correct 1062 ms 89012 KB Output is correct
15 Correct 851 ms 104004 KB Output is correct
16 Correct 1300 ms 116940 KB Output is correct
17 Correct 1048 ms 88520 KB Output is correct
18 Correct 33 ms 6788 KB Output is correct
19 Correct 1217 ms 108244 KB Output is correct
20 Correct 956 ms 80448 KB Output is correct
21 Correct 826 ms 64712 KB Output is correct
22 Correct 694 ms 56644 KB Output is correct
23 Correct 617 ms 44996 KB Output is correct
24 Correct 700 ms 53820 KB Output is correct
25 Correct 629 ms 43528 KB Output is correct
26 Correct 1369 ms 96164 KB Output is correct
27 Correct 1635 ms 125508 KB Output is correct
28 Correct 1326 ms 94276 KB Output is correct
29 Correct 926 ms 51516 KB Output is correct
30 Correct 1533 ms 111824 KB Output is correct
31 Correct 1562 ms 114152 KB Output is correct
32 Correct 1568 ms 114656 KB Output is correct
33 Correct 1312 ms 94692 KB Output is correct
34 Correct 1343 ms 94820 KB Output is correct
35 Correct 1332 ms 95140 KB Output is correct
36 Correct 981 ms 58288 KB Output is correct
37 Correct 971 ms 57160 KB Output is correct
38 Correct 980 ms 55472 KB Output is correct
39 Correct 808 ms 41684 KB Output is correct
40 Correct 785 ms 40956 KB Output is correct
41 Correct 775 ms 40368 KB Output is correct
42 Correct 761 ms 39124 KB Output is correct
43 Correct 756 ms 38532 KB Output is correct
44 Correct 760 ms 38016 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 43 ms 11888 KB Output is correct
4 Correct 6 ms 5196 KB Output is correct
5 Correct 41 ms 12696 KB Output is correct
6 Correct 32 ms 12860 KB Output is correct
7 Correct 36 ms 12948 KB Output is correct
8 Correct 39 ms 11332 KB Output is correct
9 Correct 51 ms 17176 KB Output is correct
10 Correct 45 ms 12096 KB Output is correct
11 Correct 41 ms 11940 KB Output is correct
12 Correct 53 ms 14348 KB Output is correct
13 Correct 47 ms 12484 KB Output is correct
14 Correct 44 ms 11696 KB Output is correct
15 Correct 50 ms 12536 KB Output is correct
16 Correct 44 ms 15456 KB Output is correct
17 Correct 47 ms 14536 KB Output is correct
18 Correct 1265 ms 96208 KB Output is correct
19 Correct 1252 ms 96148 KB Output is correct
20 Correct 1265 ms 96300 KB Output is correct
21 Correct 1310 ms 95784 KB Output is correct
22 Correct 1307 ms 96448 KB Output is correct
23 Correct 1912 ms 154088 KB Output is correct
24 Correct 1885 ms 150772 KB Output is correct
25 Correct 1895 ms 150416 KB Output is correct
26 Correct 33 ms 6724 KB Output is correct
27 Correct 1094 ms 121932 KB Output is correct
28 Correct 1006 ms 121016 KB Output is correct
29 Correct 1092 ms 76136 KB Output is correct
30 Correct 1078 ms 69052 KB Output is correct
31 Correct 1062 ms 89012 KB Output is correct
32 Correct 851 ms 104004 KB Output is correct
33 Correct 1300 ms 116940 KB Output is correct
34 Correct 1048 ms 88520 KB Output is correct
35 Correct 33 ms 6788 KB Output is correct
36 Correct 1217 ms 108244 KB Output is correct
37 Correct 956 ms 80448 KB Output is correct
38 Correct 826 ms 64712 KB Output is correct
39 Correct 694 ms 56644 KB Output is correct
40 Correct 617 ms 44996 KB Output is correct
41 Correct 700 ms 53820 KB Output is correct
42 Correct 629 ms 43528 KB Output is correct
43 Correct 1380 ms 29916 KB Output is correct
44 Correct 35 ms 8132 KB Output is correct
45 Correct 147 ms 9500 KB Output is correct
46 Correct 76 ms 9620 KB Output is correct
47 Correct 710 ms 32272 KB Output is correct
48 Correct 1350 ms 33908 KB Output is correct
49 Correct 685 ms 32172 KB Output is correct
50 Correct 664 ms 31460 KB Output is correct
51 Correct 656 ms 31460 KB Output is correct
52 Correct 653 ms 31428 KB Output is correct
53 Correct 1014 ms 32912 KB Output is correct
54 Correct 1010 ms 32940 KB Output is correct
55 Correct 1055 ms 32876 KB Output is correct
56 Correct 639 ms 32152 KB Output is correct
57 Correct 660 ms 32096 KB Output is correct
58 Correct 1380 ms 33856 KB Output is correct
59 Correct 1379 ms 33788 KB Output is correct
60 Correct 1378 ms 34196 KB Output is correct
61 Correct 1399 ms 34100 KB Output is correct
62 Correct 1150 ms 33180 KB Output is correct
63 Correct 1167 ms 33220 KB Output is correct
64 Correct 1310 ms 33536 KB Output is correct
65 Correct 763 ms 29796 KB Output is correct
66 Correct 1369 ms 96164 KB Output is correct
67 Correct 1635 ms 125508 KB Output is correct
68 Correct 1326 ms 94276 KB Output is correct
69 Correct 926 ms 51516 KB Output is correct
70 Correct 1533 ms 111824 KB Output is correct
71 Correct 1562 ms 114152 KB Output is correct
72 Correct 1568 ms 114656 KB Output is correct
73 Correct 1312 ms 94692 KB Output is correct
74 Correct 1343 ms 94820 KB Output is correct
75 Correct 1332 ms 95140 KB Output is correct
76 Correct 981 ms 58288 KB Output is correct
77 Correct 971 ms 57160 KB Output is correct
78 Correct 980 ms 55472 KB Output is correct
79 Correct 808 ms 41684 KB Output is correct
80 Correct 785 ms 40956 KB Output is correct
81 Correct 775 ms 40368 KB Output is correct
82 Correct 761 ms 39124 KB Output is correct
83 Correct 756 ms 38532 KB Output is correct
84 Correct 760 ms 38016 KB Output is correct
85 Correct 1866 ms 100912 KB Output is correct
86 Correct 186 ms 15988 KB Output is correct
87 Correct 115 ms 20268 KB Output is correct
88 Correct 1118 ms 113032 KB Output is correct
89 Correct 1831 ms 99756 KB Output is correct
90 Correct 1135 ms 121556 KB Output is correct
91 Correct 1375 ms 98724 KB Output is correct
92 Correct 1360 ms 98628 KB Output is correct
93 Correct 1944 ms 136552 KB Output is correct
94 Correct 1560 ms 100088 KB Output is correct
95 Correct 1592 ms 100156 KB Output is correct
96 Correct 1880 ms 140932 KB Output is correct
97 Correct 897 ms 65660 KB Output is correct
98 Correct 885 ms 62328 KB Output is correct
99 Correct 1869 ms 102200 KB Output is correct
100 Correct 1855 ms 100840 KB Output is correct
101 Correct 1912 ms 101160 KB Output is correct
102 Correct 1902 ms 101040 KB Output is correct
103 Correct 2089 ms 146208 KB Output is correct
104 Correct 2033 ms 145764 KB Output is correct
105 Correct 1472 ms 73604 KB Output is correct
106 Correct 1182 ms 53540 KB Output is correct
107 Correct 1415 ms 80124 KB Output is correct
108 Correct 1896 ms 135876 KB Output is correct
109 Correct 1371 ms 137744 KB Output is correct