QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165182#5410. 树特卡克林Lynkcat#20 151ms3896kbC++203.7kb2023-09-05 16:29:462024-07-04 02:41:25

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:41:25]
  • 评测
  • 测评结果:20
  • 用时:151ms
  • 内存:3896kb
  • [2023-09-05 16:29:46]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 5005
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
int n,m;
int ffa[N],rt[N];
poly G[N];
int s[N],siz[N],son[N];
poly all;
int mx[N];
tree<pa, null_type, less<pa>, rb_tree_tag, tree_order_statistics_node_update> t;
void dfs(int k,int fa)
{
    ffa[k]=fa;
    rt[k]=rt[fa];
    for (auto u:G[k])
    {
        if (u==fa) continue;
        dfs(u,k);
    }
} 
void makert(int k)
{
    rt[k]=k;
    dfs(k,k);
}
void gt(int k,int fa)
{
    s[k]=k;
    siz[k]=1;son[k]=0;
    mx[k]=k;
    for (auto u:G[k])
    {
        if (u==fa) continue;
        // cout<<k<<"->"<<u<<endl;
        gt(u,k);
        siz[k]+=siz[u];
        if (siz[u]>siz[son[k]]||siz[u]==siz[son[k]]&&mx[u]>mx[son[k]]) son[k]=u;
    }
    mx[k]=max(mx[k],mx[son[k]]);
    for (auto u:G[k])
    {
        if (u==fa) continue;
        if (u!=son[k]) all.push_back(s[u]);
        else s[k]^=s[u];
    }
}
void BF()
{
    for (int i=1;i<=n;i++) rt[i]=i;
    for (int i=1;i<=m;i++)
    {
        int op;
        cin>>op;
        if (op==1)
        {
            int x,y;
            cin>>x>>y;
            G[y].push_back(x);
            G[x].push_back(y);
            makert(rt[x]);
        }
        else
        {
            int x,y;
            cin>>x>>y;
            if (ffa[x]==y) swap(x,y);
            G[x].erase(find(G[x].begin(),G[x].end(),y));
            G[y].erase(find(G[y].begin(),G[y].end(),x));
            makert(y);
        }
        int k;
        cin>>k;
        for (int j=1;j<=n;j++)
            if (rt[j]==j) gt(j,j),all.push_back(s[j]);
        sort(all.begin(),all.end());
        cout<<all[(k-1)%all.size()]<<'\n';
        poly().swap(all);
    }
}
inline int tp(int k)
{
    while (ffa[k]!=k)
    {
        if (son[ffa[k]]!=k) return k;
        k=ffa[k];
    }
    return k;
}
void jump(int k)
{
    if (ffa[k]==k) 
    {
        t.insert(mp(s[k],k));
        return;
    }
    if (son[ffa[k]]==k)
    {
        jump(ffa[k]);
        return;
    }
    // cout<<","<<siz[k]<<" "<<siz[son[ffa[k]]]<<endl;
    if (!son[ffa[k]]||siz[k]>siz[son[ffa[k]]]||siz[k]==siz[son[ffa[k]]]&&mx[k]>mx[son[ffa[k]]])
    {
        int fa=ffa[k];
        t.erase(mp(s[tp(fa)],tp(fa)));
        if (son[fa])
        {
            s[tp(fa)]^=s[son[fa]];
            t.insert(mp(s[son[fa]],son[fa]));
        }
        son[fa]=k;
        s[tp(k)]^=s[k];
        // t.insert(mp(s[tp(k)],tp(k)));
        jump(fa);
    }
    else
    {
        t.insert(mp(s[k],k));
    }
}
void BF1()
{
    for (int i=1;i<=n;i++) ffa[i]=i,rt[i]=i,s[i]=i,mx[i]=i,siz[i]=1,t.insert(mp(s[i],i));
    for (int i=1;i<=m;i++)
    {
        int op;
        cin>>op;
        if (op==1)
        {
            int x,y;
            cin>>x>>y;
            ffa[y]=x;
            rt[y]=rt[x];
            int u=x;
            while (ffa[u]!=u) siz[u]+=siz[y],u=ffa[u];
            siz[u]+=siz[y];
            t.erase(mp(s[y],y));
            jump(y);
        }
        else
        {
            int x,y;
        }
        int k;
        cin>>k;
        // for (auto u:t) cout<<u.fi<<" "<<u.se<<endl;
        cout<<(*t.find_by_order((k-1)%t.size())).fi<<'\n';
    }
}
void BellaKira()
{
    cin>>n>>m;
    if (n<=1000&&m<=5000) BF();
    else BF1();
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 3668kb

input:

10 50
1 4 5 8
1 2 10 6
1 7 10 1
1 2 5 7
1 1 5 1
1 8 3 1
1 5 3 3
1 1 9 3
0 10 2 8
1 10 1 6
0 1 10 1
0 4 5 9
1 8 4 9
0 3 5 3
0 10 7 6
1 1 4 1
0 4 8 3
1 5 6 2
1 10 7 1
1 2 7 1
0 2 7 8
0 4 1 10
1 7 2 6
1 2 4 2
1 2 3 4
0 5 6 7
1 8 6 1
0 2 7 7
1 10 3 1
0 3 8 5
0 2 4 7
1 4 10 9
0 1 9 8
0 2 3 1
1 10 8 4
1 1...

output:

9
8
1
1
3
4
9
9
4
9
2
6
11
9
15
6
6
2
2
4
2
9
4
6
10
6
4
13
1
4
1
14
14
3
7
4
7
3
9
8
4
7
8
4
3
3
7
7
5
2

result:

ok 50 numbers

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 5
Accepted
time: 2ms
memory: 3708kb

input:

100 500
1 38 34 84
1 71 2 8
1 22 1 89
1 70 2 7
1 100 15 69
1 97 86 77
1 84 39 47
1 21 43 73
1 100 1 64
1 69 99 42
1 19 8 25
1 29 70 91
1 38 1 45
1 92 63 5
1 54 83 94
1 5 12 41
1 73 91 90
1 100 32 10
1 43 38 2
1 73 96 65
1 67 94 26
1 21 31 65
1 22 37 42
1 85 37 12
1 3 46 84
1 69 88 28
1 92 82 87
1 54...

output:

85
8
92
7
74
81
51
79
68
47
28
4
52
7
10
49
9
14
4
77
30
77
50
16
9
36
13
14
30
13
4
10
52
7
34
41
63
60
29
14
62
78
74
40
42
27
51
24
6
24
66
33
27
40
48
76
24
13
14
112
40
33
44
41
47
68
80
33
49
112
76
99
45
65
90
22
51
30
33
59
65
22
50
22
50
63
67
51
58
50
45
3
75
41
74
64
1
7
51
10
42
22
76
49...

result:

ok 500 numbers

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #3:

score: 10
Accepted
time: 151ms
memory: 3896kb

input:

1000 5000
1 481 556 393
1 197 951 694
1 844 89 877
1 996 276 422
1 936 284 893
1 606 205 37
1 908 355 156
1 580 338 612
1 889 574 90
1 835 998 105
1 795 673 814
1 286 226 514
1 393 557 950
1 548 913 346
1 714 779 585
1 509 140 1000
1 85 564 274
1 576 820 932
1 246 536 8
1 361 356 299
1 430 364 650
1...

output:

393
697
881
425
896
37
157
623
91
106
819
520
962
352
595
16
280
948
8
307
666
567
563
103
151
5
384
680
260
88
449
313
932
965
62
722
663
823
798
704
527
409
926
463
611
290
99
675
749
6
486
721
550
42
268
994
125
243
158
524
586
934
947
716
108
478
300
759
931
754
992
263
261
784
13
631
229
724
14...

result:

ok 5000 numbers

Subtask #4:

score: 0
Runtime Error

Test #4:

score: 0
Runtime Error

input:

100000 99999
1 1 2 44734
1 2 3 61340
1 1 4 68331
1 2 5 86313
1 4 6 26991
1 4 7 72397
1 3 8 24098
1 5 9 31437
1 5 10 82367
1 5 11 20958
1 11 12 38919
1 12 13 87596
1 2 14 41335
1 1 15 78828
1 14 16 73861
1 9 17 81368
1 1 18 40205
1 9 19 60737
1 4 20 9347
1 5 21 84645
1 18 22 20063
1 15 23 98769
1 15 ...

output:

4695
1294
3281
1247
1979
2358
4094
1436
2356
959
3925
2620
1350
3850
3897
1425
238
782
4359
4702
89
3875
3171
38
3325
4539
3260
3157
2227
4684
3313
2733
1908
5004
2253
2116
248
951
842
2498
1682
1238
1473
4118
2043
829
1290
2702
3565
4541
1019
3404
3028
689
4858
3806
2808
1597
3198
2956
2096
4704
56...

result:


Subtask #5:

score: 0
Runtime Error

Test #5:

score: 0
Runtime Error

input:

100000 99999
1 2 1 30000
1 3 2 76304
1 4 1 35053
1 5 4 38046
1 6 4 43843
1 7 1 64206
1 8 6 52957
1 9 3 42768
1 10 8 6520
1 11 5 43975
1 12 1 64810
1 13 12 64219
1 14 10 78432
1 15 4 62142
1 16 15 235
1 17 3 77806
1 18 17 58130
1 19 5 47941
1 20 14 19568
1 21 7 99780
1 22 17 39362
1 23 4 10525
1 24 1...

output:

4976
1246
27
3028
3822
4173
2941
2765
1526
3990
4829
4251
3486
2187
245
2876
3196
2997
4598
4926
4424
552
486
4439
4608
62
2269
3903
3452
579
477
2731
2244
1392
4164
4079
114
3343
4107
1969
1029
574
162
3859
1346
697
1088
252
287
613
1976
3801
2019
4915
1407
2519
4043
3249
4995
3069
485
1876
3416
37...

result:


Subtask #6:

score: 0
Runtime Error

Dependency #3:

100%
Accepted

Test #6:

score: 0
Runtime Error

input:

100000 500000
1 80697 84881 19262
1 95888 80521 10177
1 94305 51186 64430
1 98326 42972 48338
1 12913 26290 94592
1 72437 16368 33161
1 90564 19898 47803
1 72637 75741 79240
1 36415 11660 46397
1 96674 79314 69371
1 5150 54843 2612
1 33519 46498 64905
1 83708 94254 81506
1 51872 64932 91946
1 63852 ...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%