8.15集训

Posted on Edited on In

做题

码风没调，题解没写，日后补 ### 魔法少女

click

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define lson l, mid, ls[x]
#define rson mid+1, r, rs[x]
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 4e5+66;

int ls[N * 19], rs[N * 19], si[N * 19];
int n, tot, f[N], root[N], tag[N * 19];
int m = 1e9;
double sum[N * 19];

inline void pushdown(int x) {
    if (tag[x]) {
        si[ls[x]] = si[rs[x]] = 0;
        sum[ls[x]] = sum[rs[x]] = 0;
        tag[ls[x]] = tag[rs[x]] = 1;
        tag[x] = 0;
    }
}

inline int find(int x) {return f[x] == x ? f[x] : f[x] = find(f[x]);}

inline void add(int p, int a, double v, int l, int r, int &x)
{
    if (!x) x = ++ tot;
    si[x] += a, sum[x] += a*v;
    if (l == r) return;
    pushdown(x);
    int mid = (l + r) >> 1;
    if (p <= mid) add(p, a, v, lson);
    else add(p, a, v, rson);
}

inline void del(int b, int e, int l, int r, int x) 
{
    if (!x) return;
    if (b <= l && r <= e)
    {
        si[x] = 0, sum[x] = 0, tag[x] = 1;
        return;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (b <= mid) del(b, e, lson);
    if (e > mid) del(b, e, rson);
    si[x] = si[ls[x]] + si[rs[x]];
    sum[x] = sum[ls[x]] + sum[rs[x]];
}

inline int querysi(int b, int e, int l, int r, int x)
{
    if (!x) return 0;
    if (b <= l && r <= e) return si[x];
    pushdown(x);
    int mid = (l + r) >> 1, res = 0;
    if (b <= mid) res += querysi(b, e, lson);
    if (e > mid) res += querysi(b, e, rson);
    return res;
}

inline int find(int k, int l, int r, int x)
{
    if (l == r) return l;
    pushdown(x);
    int mid = (l + r) >> 1;
    if (k <= si[ls[x]]) return find(k, lson);
    else return find(k - si[ls[x]], rson);
}

inline int merge(int x, int y) 
{
    if (!x || !y) return x+y;
    si[x] += si[y], sum[x] += sum[y];
    pushdown(x);
    pushdown(y);
    ls[x] = merge(ls[x], ls[y]);
    rs[x] = merge(rs[x], rs[y]);
    return x;
}


inline int thestars()
{
    int T, c, x, y, t;
    scanf ("%d", &T);
    while (T --)
    {
        scanf ("%d%d", &c, &x);
        switch(c)
        {
            case 1: add(x, 1, log(x), 1, m, root[++ n]), f[n] = n; break;
            case 2:
            {
                scanf ("%d", &y);
                x = find(x), y = find(y);
                if (x != y)
                {
                    f[y] = x;
                    root[x] = merge(root[x], root[y]);
                }
                break;
            }
            case 3:
            {
                x = find(x); scanf ("%d", &y);
                t = querysi(1, y, 1, m, root[x]);
                del(1, y, 1, m, root[x]);
                add(y, t, log(y), 1, m, root[x]);
                break;
            }
            case 4:
            {
                x = find(x);  scanf ("%d", &y);
                t = querysi(y, m, 1, m, root[x]);
                del(y, m, 1, m, root[x]);
                add(y, t, log(y), 1, m, root[x]);
                break;

            }
            case 5: 
            {
                x = find(x); scanf ("%d", &y);
                cout << find(y, 1, m, root[x]) << '\n';
                break;
            }
            case 6:
            {
                x = find(x); scanf ("%d", &y);
                y = find(y);
                printf("%d\n", sum[root[x]] > sum[root[y]]);
                break;
            }
            default : x = find(x); cout << si[root[x]] << '\n';
        }
    }
    return 0;
}

int youngore = thestars();

signed main() {;}

大陆争霸

click

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
typedef pair<int, int> pr;
const int N = 1e5+66;

priority_queue<pr, vector<pr>, greater<pr> >q;
vector<int>p[N];

int to[N], nex[N], head[N], cnt;
int len[N], c[N];
int f[N], g[N], v[N];

inline void add(int x, int y, int z) {
    to[++ cnt] = y;
    len[cnt] = z;
    nex[cnt] = head[x];
    head[x] = cnt;
}

inline int thestars()
{
    memset(f, 0x3f, sizeof f), memset(g, 0x3f, sizeof g);
    int i, j, k, n, m, res(0);
    int x, y, z;
    scanf ("%d%d", &n, &m);
    for (i = 1; i <= m; ++ i)
    {
        scanf ("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    for (i = 1; i <= n; ++ i)
    {
        scanf ("%d", c + i);
        for (j = 1; j <= c[i]; ++ j)
        {
            scanf ("%d", &x);
            p[x].push_back(i);
        }
        if (!c[i]) g[i] = 0;
    }
    f[1] = 0, q.push(pr(0, 1));
    while (!q.empty()) 
    {
        z = q.top().first, x = q.top().second, q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (i = head[x]; i; i = nex[i])
        {
            y = to[i];
            if (f[y] > z + len[i])
            {
                f[y] = z + len[i];
                if (!c[y]) q.push(pr(max(f[y], g[y]), y));
            }
        }
        for (i = 0; i < (int)p[x].size(); ++ i)
        {
            y = p[x][i];
            -- c[y];
            if (!c[y])
            {
                g[y] = z;
                q.push(make_pair(max(f[y], g[y]), y));
            }
        }
    }
    cout << max(f[n], g[n]);
    return 0;
}

int youngore = thestars();

signed main() {;}

小猪

click

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//bu bi yong vector
// dui x qu chu low
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e6+66;

struct edge{int to, nex;}e[N]; int head[N], bian;

inline void add(int x, int y)
{
    e[++ bian].to = y;
    e[bian].nex = head[x];
    head[x] = bian;
}

int dfn[N], low[N], sta[N], in[N], tar[N];
int tp, tot, cnt, cd[N];

inline void tarjan(int x) {
    int i, y;
    dfn[x] = low[x] = ++ tot;
    sta[++ tp] = x, in[x] = 1;
    for (i = head[x]; i; i = e[i].nex)
    {
        y = e[i].to;
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } 
        else if (in[y]) low[x] = min(low[x], dfn[y]);
    }
    if (low[x] == dfn[x])
    {
        ++ cnt;
        do {
            y = sta[tp --];
            in[y] = 0;
            tar[y] = cnt;
        } while (y != x);
    }
}

inline int thestars()
{
    int i, j, x, y, n, res(0);
    cin >> n;
    for (i = 1; i <= n; ++ i) scanf ("%d", &x), add(i, x);
    for (i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i);
    for (x = 1; x <= n; ++ x)
    {
        for (i = head[x]; i; i = e[i].nex)
        {
            y = e[i].to;
            if (tar[x] == tar[y]) continue;
            else cd[tar[x]] = 1;
        }
    }
    for (i = 1; i <= cnt; ++ i) if (!cd[i]) ++ res;
    cout << res;
    return 0;
}

int youngore = thestars();

signed main() {;}

食物链

click

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 5e5+66;
 
queue<int>q;
int rd[N], cd[N], f[N];
int to[N], nex[N], head[N], cnt;

inline void add(int x, int y)
{
    to[++ cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt;
}
//f[i] has showed that from which zero to i's ways
inline int thestars()
{
    int i, x, y, n, m, res(0);
    cin >> n >> m;
    for (i = 1; i <= m; ++ i)
    {
        scanf ("%lld%lld", &x, &y);
        add(x, y);
        ++ rd[y];
        ++ cd[x];
    }
    for (i = 1; i <= n; ++ i)
    {
        if (!rd[i]) 
        {
            if (cd[i]) f[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty())
    {
        x = q.front(); q.pop();
        for (i = head[x]; i; i = nex[i])
        {
            y = to[i];
            f[y] += f[x];
            -- rd[y];
            if (!rd[y]) q.push(y);
        }
    }
    for (i = 1; i <= n; ++ i) if (!cd[i]) res += f[i];
    cout << res;
    return 0;
}

int youngore = thestars();

signed main() {;}

BLO

click

割点经典好题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 5e5+66;

int to[N<<1], head[N<<1], nex[N<<1], cnt;

inline void add(int x, int y)
{
    to[++ cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt;
}

int low[N], dfn[N], si[N], cut[N];
int n, m, tot;
LL ans[N];

inline void tarjan(int x) 
{
    int i, y;
    low[x] = dfn[x] = ++ tot, si[x] = 1;
    int flag(0), sum(0);
    for (i = head[x]; i; i = nex[i])
    {
        y = to[i];
        if (! dfn[y])
        {
            tarjan(y);
            si[x] += si[y];
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x])
            {
                ++ flag;
                ans[x] += (LL)si[y] * (n - si[y]);
                sum += si[y];
                if (x != 1 || flag > 1) cut[x] = 1;
            }
        } else low[x] = min(low[x], dfn[y]);
    }
    if (cut[x]) ans[x] += (LL)(n - sum - 1) * (sum + 1) + (n - 1);
    //dui yu ge dian (n-1) duiying dandu yige dian deqingkuang
    //yijingjisuanle size[s1....sk]de qingkuang
    //(n - sum - 1) * (sum + 1)shi nage zitu
    else ans[x] = (n - 1)<<1;
}

inline int thestars()
{
    int i, x, y;
    cin >> n >> m;
    cnt = 1;
    for (i = 1; i <= m; ++ i){
        scanf ("%d%d", &x, &y);
        if (x == y) continue;
        add(x, y);
        add(y, x);
    }
    tarjan(1);
    for (i = 1 ; i <= n; ++ i) cout << ans[i] << '\n';
    return 0;
}

int youngore = thestars();

signed main() {;}