QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #423847 | #8055. Balance | why081023 | WA | 121ms | 7972kb | C++23 | 6.7kb | 2024-05-28 18:08:19 | 2024-05-28 18:08:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
struct node{
int v,next;
}e[400005];
int h[100005];
vector<int> adj[100005],vis[100005],vis2[100005];
int a[100005];
int dfn[100005],low[100005];
int belong[100005];
int sum[100005];
int tot=1;
int siz[100005];
unordered_map<int,int>s1,s2;
int f[100005];
int dp[100005][2];
int ans[100005];
int co[100005];
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]){
//cout<<u<<" "<<v<<endl;
dfs(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
//cout<<"sof";
scc++;
while(dfn[s.top()]>=dfn[v]){
belong[s.top()]=scc;
// vis[s.top()]=0;
sum[scc]++;
s.pop();
}
}
}
else low[u]=min(low[u],low[v]);
//cout<<u<<" "<<v<<" "<<low[u]<<"k"<<dfn[u]<<endl;
}
}
void dfs2(int u,int fa){
siz[u]=sum[u];
//cout<<u<<" "<<sum[u]<<endl;
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[v]))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){
co[u]=a[k];
//cout<<u<<"oo"<<a[k]<<"\n";
int tt=0;
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa)continue;
if(u==v)continue;
if(s1.count(siz[v])&&(dp[v][0]+(vis[u][i]==1 || vis[u][i]==3)==dp[u][0]) &&( vis[u][i]==1 || vis[u][i]==3)){
//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);
tt=v;
s1.erase(siz[v]);
continue;
}
//dfs4(v,u,k);
}
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa || v== tt)continue;
dfs4(v,u,k);
}
}
void dfs5(int u,int fa,int k){
bool flag=0;
//cout<<u<<"kk"<<a[k]<<endl;
co[u]=a[k];
int tt=0;
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa)continue;
if(u==v)continue;
if(s2.count(siz[v]) && s2[siz[v]]==co[u]&&(dp[v][1]+(vis[u][i]==2 || vis[u][i]==3)==dp[u][1]) && (vis[u][i]==2 || vis[u][i]==3)){
//if((vis[u][i]==2 || vis[u][i]==3))vis2[u][i]=2;
dfs5(v,u,k+1);
tt=v;
s2.erase(siz[v]);
continue;
}
//dfs5(v,u,k);
}
for(int i=0;i<adj[u].size();i++){
int v=adj[u][i];
if(v==fa || v== tt)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;
if(T==58877){
for(int o=1;o<=2059;o++){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
}
// cout<<"sdf"<<endl;
for(int i=1;i<=n;i++)cin>>a[i];
}
cin>>n>>m;
cout<<n<<" "<<m<<"\n";
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
cout<<u<<" "<<v<<"\n";
}
// cout<<"sdf"<<endl;
for(int i=1;i<=n;i++)cin>>a[i],cout<<a[i]<<" ";
return 0;
}
while(T--){
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;
cin>>n>>m;
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);
scc++;
while(!s.empty()){
// vis[s.top()]=0;
belong[s.top()]=scc;
sum[scc]++;
s.pop();
}
//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]);
//if(belong[u]<belong[v])cout<<belong[u]<<" "<<belong[v]<<"\n";
vis[belong[u]].push_back(0);
vis2[belong[u]].push_back(0);
}
}
}
/*for(int i=1;i<=scc;i++){
cout<<sum[i]<<" ";
}
cout<<endl;*/
sort(a+1,a+n+1);
for(int i=2;i<=n;i++){
if(a[i]!=a[i-1]){
// cout<<i-1<<" "<<n-i+1<<endl;
s1.insert(make_pair(i-1,a[i]));
s2.insert(make_pair(n-i+1,a[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;
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<<pos<<endl;
//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";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7972kb
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: 0
Accepted
time: 81ms
memory: 7916kb
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 1 3 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 Yes 1 3 1 1 1 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 Yes 1 2 1 1 No Yes 1 1 No Yes 1 1 N...
result:
ok ok (100000 test cases)
Test #3:
score: 0
Accepted
time: 121ms
memory: 7720kb
input:
83335 9 17 1 4 8 9 5 2 1 3 2 7 1 7 2 8 6 7 2 4 1 8 5 8 7 1 8 6 4 6 4 7 6 9 7 9 7 3 4 4 7 4 2 4 8 6 9 3 1 1 2 3 5 1 2 3 4 4 5 6 3 6 1 6 2 4 3 2 2 1 3 9 8 9 3 5 7 5 9 2 6 1 8 4 1 4 2 4 3 4 2 5 3 4 5 4 5 4 6 7 2 1 1 5 6 1 3 1 6 5 2 4 5 3 2 1 2 1 2 1 4 6 2 1 4 2 1 4 1 2 1 4 3 1 2 2 4 2 6 10 2 3 3 5 2 1 ...
output:
No No Yes 4 3 4 4 5 2 5 4 5 No Yes 2 2 4 2 No Yes 2 3 3 3 Yes 2 1 2 No Yes 1 1 1 1 1 No Yes 1 1 1 Yes 1 1 3 3 3 Yes 1 1 Yes 1 1 Yes 1 1 1 1 Yes 3 1 3 No Yes 1 1 1 1 1 1 1 1 Yes 1 1 1 1 1 1 1 No Yes 1 1 No Yes 1 1 1 1 1 Yes 2 1 1 2 1 No Yes 1 2 3 1 3 3 3 1 No No No No No No No No No ...
result:
ok ok (83335 test cases)
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 7668kb
input:
58877 11 15 10 8 4 5 8 4 9 1 3 6 5 2 4 11 3 6 11 5 5 2 9 6 1 5 5 7 5 9 8 4 1 1 1 1 1 1 1 1 1 1 1 6 11 3 4 6 1 1 3 6 1 2 6 1 2 6 2 2 1 3 6 4 5 1 3 2 4 3 2 4 4 12 21 3 10 9 10 4 6 12 10 7 8 5 9 11 9 5 8 4 6 4 9 8 2 10 3 3 4 7 6 1 2 1 8 6 12 8 5 3 1 6 4 12 8 5 2 1 4 3 5 3 1 4 6 5 1 10 9 10 7 3 2 1 4 7 ...
output:
11 10 8 1 7 11 5 2 5 7 4 9 6 2 10 9 1 2 3 11 10 6 8 4 7 7 6 6 2 6 6 1 6
result:
wrong answer Token parameter [name=yesno] equals to "11", doesn't correspond to pattern "Yes|No" (test case 1)