QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #377580 | #8055. Balance | comld | WA | 110ms | 75340kb | C++14 | 5.0kb | 2024-04-05 15:30:20 | 2024-04-05 15:30:21 |
Judging History
answer
#include<bits/stdc++.h>
#define N 400009
using namespace std;
typedef long long ll;
int low[N],dfn[N];
int head[N],siz[N],f[N],br[N],tot=1,tr1[N],tag[N];
int t,si[N],siz1[N],siz2[N],dp1[N],dp2[N],tr2[N];
vector<int>vec[N],ve1[N],ve2[N];
int num=0,n,m,a[N],b[N],c[N],sum1[N],sum2[N],pos[N];
vector<int>::iterator it1;
map<int,int>mp[N],mp1,mp2;
map<int,int>::iterator it;
struct edge{
int n,to;
}e[N];
int find(int x){
return f[x]=f[x]==x?x:find(f[x]);
}
inline void add(int u,int v){
e[++tot].n=head[u];
e[tot].to=v;
head[u]=tot;
}
void add1(int u,int v){
vec[u].push_back(v);
vec[v].push_back(u);
}
void tarjan(int u,int edge){
dfn[u]=low[u]=++t;
for(int i=head[u];i;i=e[i].n) {
int v=e[i].to;
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])br[i]=br[i^1]=1;
}
else if(i!=(edge^1))low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u,int fa){
siz1[u]=si[u];
siz2[u]=1;
dfn[u]=++dfn[0];
pos[dfn[0]]=u;
for(auto v:vec[u])if(v!=fa){
dfs(v,u);
siz1[u]+=siz1[v];
siz2[u]+=siz2[v];
}
if(mp1[siz1[u]]){
int ok=0;
int x=mp1[siz1[u]];
if(x==1){
ok=1;
}
else{
it1=lower_bound(ve1[x-1].begin(),ve1[x-1].end(),dfn[u]);
if(it1!=ve1[x-1].end()&&((*it1)<=dfn[u]+siz2[u]-1)) {
ok=1;
tr1[u]=pos[*it1];
}
}
if(ok)ve1[x].push_back(dfn[u]),dp1[u]=x;
}
if(mp2[siz1[u]]){
int ok=0;
int x=mp2[siz1[u]];
if(x==num){
ok=1;
}
else{
it1=lower_bound(ve2[x+1].begin(),ve2[x+1].end(),dfn[u]);
if(it1!=ve2[x+1].end()&&((*it1)<=dfn[u]+siz2[u]-1)) {
ok=1;
tr2[u]=pos[*it1];
}
}
if(ok)ve2[x].push_back(dfn[u]),dp2[u]=x;
}
}
inline void sol1(int x,int y){
for(int i=y-1;i>=1;--i){
x=tr1[x];
tag[x]=i;
}
}
inline void sol2(int x,int y){
for(int i=y+1;i<=num;++i){
x=tr2[x];
tag[x]=i;
}
}
void dfs2(int u,int fa){
if(!tag[u])tag[u]=tag[fa];
for(auto v:vec[u])if(v!=fa){
dfs2(v,u);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin>>T;
int bb=0;
while(T--){
cin>>n>>m;
int u,v;
bb++;
for(int i=1;i<=m;++i) {
cin>>u>>v;
if(bb==15)cout<<u<<" "<<v<<endl;
add(u,v);
add(v,u);
}
tarjan(1,0);
for(int u=1;u<=n;++u)f[u]=u;
for(int u=1;u<=n;++u) {
for(int i=head[u];i;i=e[i].n)if(br[i]==0){
int v=e[i].to;
int xx=find(u),yy=find(v);
if(xx!=yy) {
f[xx]=yy;
}
}
}
for(int u=1;u<=n;++u)si[find(u)]++;
for(int u=1;u<=n;++u) {
for(int i=head[u];i;i=e[i].n)if(br[i]==1){
int v=e[i].to;
int xx=find(u),yy=find(v);
if(mp[xx].find(yy)==mp[xx].end()) {
mp[xx][yy]=1;
mp[yy][xx]=1;
add1(xx,yy);
}
}
}
for(int i=0;i<=n;++i)dfn[i]=0;
for(int i=1;i<=n;++i)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
if(i==1||a[i]!=a[i-1]){
++num;
b[num]=a[i];
c[num]=1;
}
else c[num]++;
}
if(bb==15){
for(int i=1;i<=n;++i)cout<<a[i]<<" ";cout<<endl;
}
for(int i=1;i<=num;++i){
sum1[i]=sum1[i-1]+c[i];
mp1[sum1[i]]=i;
}
for(int i=num;i>=1;--i){
sum2[i]=sum2[i+1]+c[i];
mp2[sum2[i]]=i;
}
dfs(find(1),0);
// for(int i=1;i<=n;++i)if(find(i)==i)cout<<dp1[i]<<" ? "<<dp2[i]<<endl;
int ok=0;
if(num==1){
for(int i=1;i<=n;++i)tag[i]=b[1];
ok=1;
}
if(ok==0)
for(int i=1;i<=n;++i)if(find(i)==i){
if(dp1[i]==num-1){
tag[i]=num-1;
tag[find(1)]=num;
ok=1;
sol1(i,num-1);
break;
}
if(dp2[i]==2){
tag[i]=2;
tag[find(1)]=1;
ok=1;
sol2(i,2);
break;
}
}
if(ok==0)
for(int i=1;i<=n;++i)if(find(i)==i){
if(dp1[i]) {
int x=dp1[i]+2;
it1=lower_bound(ve2[x].begin(),ve2[x].end(),dfn[i]+siz2[i]);
if(it1!=ve2[x].end()){
int y=pos[*it1];
tag[find(1)]=x-1;
tag[i]=dp1[i];
tag[y]=x;
ok=1;
sol1(i,dp1[i]);
sol2(y,x);
break;
}
}
if(dp2[i]) {
int x=dp2[i]-2;
if(x<0)continue;
it1=lower_bound(ve1[x].begin(),ve1[x].end(),dfn[i]+siz2[i]);
if(it1!=ve1[x].end()){
int y=pos[*it1];
tag[find(1)]=x+1;
tag[i]=dp2[i];
tag[y]=x;
ok=1;
sol2(i,dp2[i]);
sol1(y,x);
// cout<<i<<" "<<x<<" "<<(*it1)<<endl;
break;
}
}
}
if(ok==0){
cout<<"No\n";
}
else{
cout<<"Yes\n";
dfs2(find(1),0);
for(int i=1;i<=n;++i) {
cout<<tag[find(i)]<<" ";
}
cout<<'\n';
}
for(int i=0;i<=n;++i){
low[i]=dfn[i]=head[i]=siz[i]=f[i]=sum1[i]=sum2[i]=pos[i]=0;
tot=1;
tr1[i]=tr2[i]=tag[i]=si[i]=siz1[i]=siz2[i]=dp1[i]=dp2[i]=0;
vec[i].clear();ve1[i].clear();ve2[i].clear();
mp[i].clear();
}
for(int i=0;i<=m*2+2;++i)br[i]=0;
mp1.clear();mp2.clear();
t=num=0;
//int head[N],siz[N],f[N],br[N],tot=1,tr1[N],tag[N];
//int t,si[N],siz1[N],siz2[N],dp1[N],dp2[N],tr2[N];
//vector<int>vec[N],ve1[N],ve2[N];
//int num=0,n,m,a[N],b[N],c[N],sum1[N],sum2[N],pos[N];
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 75340kb
input:
5 5 4 1 2 2 3 3 4 4 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 2 2 3 5 6 1 2 1 2 2 3 3 4 4 5 3 5 1 2 1 2 1 2 2 1 2 1 2 1 2
output:
Yes 5 4 3 2 1 No Yes 2 3 1 2 2 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 73300kb
input:
100000 4 3 4 2 1 3 2 1 2 1 3 2 5 7 2 5 5 3 2 3 5 1 4 3 2 4 4 3 1 3 1 1 2 3 2 2 1 2 3 1 1 1 4 7 3 4 1 4 2 3 4 3 4 2 3 1 4 3 2 3 3 2 4 6 2 4 3 1 1 2 1 2 2 3 4 2 1 1 3 3 4 7 3 2 4 2 1 2 3 4 3 2 2 4 3 4 2 1 1 1 5 5 3 2 1 5 4 5 4 3 2 1 1 2 2 3 2 3 5 2 3 1 3 3 1 3 1 2 1 3 2 3 2 3 2 1 2 1 1 2 1 1 2 3 2 1 1...
output:
Yes 2 2 3 1 No Yes 1 1 1 No No Yes 2 1 1 1 No No Yes 1 1 Yes 1 1 Yes 1 1 Yes 1 1 1 1 No Yes 1 1 1 1 1 1 4 1 3 4 5 4 5 1 4 2 4 3 4 1 5 3 1 1 1 1 1 3 Yes 1 2 1 1 1 Yes 1 1 1 Yes 2 1 Yes 1 1 1 1 1 Yes 2 1 No Yes 1 1 Yes 1 1 1 Yes 1 1 Yes 1 1 1 1 Yes 1 1 Yes 2 2 2 2 2 Yes 1 1 1 1 1 ...
result:
wrong answer Token parameter [name=yesno] equals to "1", doesn't correspond to pattern "Yes|No" (test case 15)