QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #422055 | #8055. Balance | why081023 | WA | 87ms | 77424kb | C++14 | 5.5kb | 2024-05-26 17:35:37 | 2024-05-26 17:35:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
struct node{
int v,next;
}e[1000005];
int h[1000005];
vector<int> adj[1000005],vis[1000005],vis2[1000005];
int a[1000005];
int dfn[1000005],low[1000005];
int belong[1000005];
int sum[1000005];
int tot=1;
int siz[1000005];
set<int>s1,s2;
int f[1000005];
int dp[1000005][2];
int ans[1000005];
int co[1000005];
void addedge(int u,int v){
e[++tot].v=v;
e[tot].next=h[u];h[u]=tot;
}
stack<int>s;
int tim;
int scc;
void dfs(int u,int go){
s.push(u);
//cout<<u<<endl;
tim++;
low[u]=dfn[u]=tim;
for(int i=h[u];i;i=e[i].next){
int v=e[i].v;
//cout<<v<<" "<<i<<" "<<dfn[v]<<endl;
if(i==(go^1))continue;
if(!dfn[v]){
dfs(v,i);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],low[v]);
}
if(low[u]==dfn[u]){
scc++;
while(s.top()!=u){
int hh=s.top();
s.pop();
sum[scc]++;
belong[hh]=scc;
}
s.pop();
belong[u]=scc;
sum[scc]++;
}
}
void dfs2(int u,int fa){
siz[u]=1;
f[u]=fa;
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa)continue;
dfs2(v,u);
siz[u]+=siz[v];
if(s1.count(siz[v]))vis[u][i]+=1;
if(s2.count(siz[u]))vis[u][i]+=2;
}
}
void dfs3(int u,int fa){
//int Max1,Max2;
int up=0,down=0;
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa)continue;
dfs3(v,u);
if(vis[u][i]==1 || vis[u][i]==3)dp[u][0]=max(dp[u][0],dp[v][0]+1);
else dp[u][0]=max(dp[u][0],dp[v][0]);
if(vis[u][i]==2 || vis[u][i]==3)dp[u][1]=max(dp[u][1],dp[v][1]+1);
else dp[u][1]=max(dp[u][1],dp[v][1]);
ans[u]=max(ans[u],up+dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
ans[u]=max(ans[u],down+dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
up=max(up,dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
down=max(down,dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
}
}
void dfs4(int u,int fa,int k){
bool flag=0;
co[u]=a[k];
//cout<<u<<"oo"<<k<<"\n";
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa)continue;
if(u==v)continue;
if((dp[v][0]+(vis[u][i]==1 || vis[u][i]==3)==dp[u][0])&& flag==0){
//cout<<u<<":"<<v<<endl;
//cout<<"asfasdfasdfasdfsadf\n";
if(vis[u][i]==1 || vis[u][i]==3)vis2[u][i]=1;
dfs4(v,u,k-1);
flag=1;
continue;
}
dfs4(v,u,k);
}
}
void dfs5(int u,int fa,int k){
bool flag=0;
//cout<<u<<" "<<k<<"kk"<<a[k]<<endl;
co[u]=a[k];
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa)continue;
if(u==v)continue;
if((dp[v][1]+(vis[u][i]==2 || vis[u][i]==3)==dp[u][1]) && flag==0){
if(vis[u][i]==2 || vis[u][i]==3)vis2[u][i]=2;
dfs5(v,u,k+1);
flag=1;
continue;
}
dfs5(v,u,k);
}
}
int flag=0;
void dfs6(int u,int fa,int k){
//cout<<u<<" "<<k<<"kk"<<a[k]<<endl;
//cout<<u<<" "<<k<<"ooo"<<"\n";
co[u]=a[k];
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa || co[v])continue;
dfs6(v,u,k);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
h[i]=a[i]=dfn[i]=0;
low[i]=belong[i]=0;
sum[i]=siz[i]=f[i]=ans[i]=co[i]=dp[i][0]=dp[i][1]=co[i]=0;
adj[i].clear(),vis[i].clear(),vis2[i].clear();
}
tot=1;
while(!s.empty())s.pop();
s1.clear();
s2.clear();
scc=0;
flag=0;
tim=0;
flag=n-1;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
// cout<<"sdf"<<endl;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0);
//for(int i=1;i<=n;i++)cout<<belong[i]<<" ";
// cout<<endl;
for(int u=1;u<=n;u++){
for(int j=h[u];j;j=e[j].next){
int v=e[j].v;
if(belong[u]!=belong[v]){
//cout<<"sad";
adj[belong[u]].push_back(belong[v]);
vis[belong[u]].push_back(0);
vis2[belong[u]].push_back(0);
}
}
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i++){
if(a[i]!=a[i-1]){
s1.insert(i-1);
s2.insert(n-i+1);
}
else flag--;
}
dfs2(1,0);
dfs3(1,0);
int Max=0,pos=0;
for(int i=1;i<=n;i++){
if(ans[i]>Max){
Max=ans[i];
pos=i;
}
//cout<<ans[i]<<endl;
}
int gg=unique(a+1,a+n+1)-a-1;
//for(int i=1;i<=gg;i++)cout<<a[i]<<"gg";
//cout<<"\n";
if(Max>=flag){
cout<<"Yes"<<"\n";
}
else {
cout<<"No"<<"\n";
continue;
}
int up=0,down=0;
int up_pos=0,down_pos=0;
int anss=0;;
int aa=0,b=0;
int t=0;
int u=pos;
for(int i=0;i<adj[pos].size();i++){
int v=adj[pos][i];
if(v==f[pos])continue;
anss=max(anss,up+dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
anss=max(anss,down+dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
// cout<<ans<<" "<<flag<<endl;
if(anss==flag){
//cout<<"dsaf"<<endl;
if(anss==up+dp[v][0]+(vis[u][i]==1 || vis[u][i]==3)){
aa=v,b=up_pos;
t=dp[v][0]+(vis[u][i]==1 || vis[u][i]==3);
}
else {
b=v;
aa=down_pos;
t=down;
}
break;
}
if(dp[v][1]+(vis[u][i]==2||vis[u][i]==3)>up){
up=max(up,dp[v][1]+(vis[u][i]==2||vis[u][i]==3));
up_pos=v;
}
if(dp[v][0]+(vis[u][i]==1 || vis[u][i]==3)>down){
down_pos=v;
down=max(down,dp[v][0]+(vis[u][i]==1 || vis[u][i]==3));
}
}
//cout<<"asdf"<<endl;
t++;
//cout<<aa<<" tt"<<b<<" "<<t<<"\n";
for(int i=0;i<adj[pos].size();i++){
int v=adj[pos][i];
if(v==aa)dfs4(aa,pos,t- (vis[u][i]==1 || vis[u][i]==3));
if(v==b)dfs5(b,pos,t+ (vis[u][i]==2 || vis[u][i]==3));
}
//dfs4(a,f[a],t),dfs5(b,f[b],t+2);
dfs6(1,0,t);
//for(int i=1;i<=n;i++)cout<<co[i]<<endl;
for(int i=1;i<=n;i++){
cout<<co[belong[i]]<<" ";
}
cout<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 77424kb
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 1 2 3 4 5 No Yes 2 2 2 1 3 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 87ms
memory: 75324kb
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 1 2 0 3 No Yes 1 1 1 No No No No No Yes 1 1 Yes 1 1 Yes 1 1 Yes 1 1 1 1 No Yes 1 1 1 1 1 No Yes 1 1 1 Yes 1 2 Yes 1 1 1 1 1 Yes 1 2 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 Yes 1 1 No No Yes 1 1 No Yes 1 1 Yes 3 2 2 2 No No Yes 1 1 2 0 0 ...
result:
wrong answer Integer parameter [name=a[i]] equals to 0, violates the range [1, 4] (test case 1)