QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#165182 | #5410. 树特卡克林 | Lynkcat# | 20 | 151ms | 3896kb | C++20 | 3.7kb | 2023-09-05 16:29:46 | 2024-07-04 02:41:25 |
Judging History
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%