QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #528706 | #8055. Balance | stasio6 | WA | 120ms | 20256kb | C++14 | 6.7kb | 2024-08-23 20:06:15 | 2024-08-23 20:06:16 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<17;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const int L=20;
int t[N],n,dep[N],lo[N],fau[N],m,l,pod[N],w[N],k1[N],k2[N],li,seg[SS*2+10],g[N];
int kol[N],t2[N],p1=0,p2=0;
pair<int,int> pre[N];
vi graf[N],graf2[N],graf3[N],kon1[N],kon2[N];
bool vis[N],d1[N],d2[N];
pair<int,int> odp;
void upd(int a,int b){
seg[a+=SS]=b;
for(a/=2;a;a/=2) seg[a]=max(seg[a*2],seg[a*2+1]);
}
int qr(int a,int b){
int res=-INFi;
for(a+=SS-1,b+=SS+1;a/2!=b/2;a/=2,b/=2){
if(a%2==0) res=max(res,seg[a+1]);
if(b%2) res=max(res,seg[b-1]);
}
return res;
}
void dfs(int v){
vis[v]=1;
for(auto u:graf[v]){
if(vis[u]) continue;
dep[u]=dep[v]+1;
dfs(u);
}
}
void dfs2(int v,int o){
vis[v]=1;
int il=0;
lo[v]=dep[v];
for(auto u:graf[v]){
if(dep[u]<dep[v]){
if(u==o){
if(il==0){
il++;
continue;
}
lo[v]=min(lo[v],dep[u]);
}else{
lo[v]=min(lo[v],dep[u]);
}
}
if(vis[u]) continue;
dfs2(u,v);
lo[v]=min(lo[u],lo[v]);
}
for(auto u:graf[v]){
if(u==o) continue;
if(lo[u]!=dep[u]){
graf2[v].push_back(u);
graf2[u].push_back(v);
}
}
}
void dfs3(int v,int s){
vis[v]=1;
fau[v]=s;
t[s]++;
for(auto u:graf2[v]){
if(vis[u]) continue;
dfs3(u,s);
}
}
void dfs4(int v,int o){
pre[v].fi=++l;
pod[v]=t[v];
for(auto u:graf3[v]){
if(u==o) continue;
dfs4(u,v);
pod[v]+=pod[u];
}
pre[v].se=l;
}
void dfs5(int v,int val){
if(d1[v] and k1[v]==p1-1){
p1--;
val=p1;
}
kol[v]=t2[val];
for(auto u:graf3[v]){
if(pod[u]>pod[v]) continue;
dfs5(u,val);
}
}
void dfs6(int v,int val){
if(d2[v] and k2[v]==p2+1){
p2++;
val=p2;
}
kol[v]=t2[val];
for(auto u:graf3[v]){
if(pod[u]>pod[v]) continue;
dfs6(u,val);
}
}
bool przodek(int a,int b){
if(pre[a].fi<=pre[b].fi and pre[a].se>=pre[b].fi) return 1;
swap(a,b);
if(pre[a].fi<=pre[b].fi and pre[a].se>=pre[b].fi) return 1;
return 0;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
graf[a].push_back(b),graf[b].push_back(a);
}
dfs(1);
for(int i=1;i<=n;i++) vis[i]=0;
dfs2(1,1);
for(int i=1;i<=n;i++) vis[i]=0;
li=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs3(i,++li);
}
}
for(int i=1;i<=n;i++){
for(auto u:graf[i]){
if(fau[i]!=fau[u]){
graf3[fau[i]].push_back(fau[u]);
}
}
}
vi xd;
for(int i=1;i<=n;i++){
int a;
cin>>a;
xd.push_back(a);
}
sort(xd.begin(),xd.end());
int kt=1,curr=0;
for(int i=0;i<xd.size();i++){
if(i>0 and xd[i]>xd[i-1]){
w[kt]=curr;
t2[kt]=xd[i-1];
kt++,curr=1;
}else curr++;
}
w[kt]=curr;
t2[kt]=xd.back();
curr=0;
for(int i=1;i<=kt;i++){
curr+=w[i];
g[curr]=i;
}
dfs4(1,1);
for(int i=1;i<=li;i++) k1[i]=g[pod[i]];
curr=0;
for(int i=1;i<=kt;i++){
curr+=w[i];
g[curr]=0;
}
curr=0;
for(int i=kt;i>=1;i--){
curr+=w[i];
g[curr]=i;
}
for(int i=1;i<=li;i++) k2[i]=g[pod[i]];
curr=0;
for(int i=kt;i>=1;i--){
curr+=w[i];
g[curr]=0;
}
vector<pair<int,int>> vp;
for(int i=1;i<=li;i++) vp.push_back({pod[i],i});
sort(vp.begin(),vp.end());
for(auto [a,u]:vp){
if(!k1[u]) continue;
int xd=qr(pre[u].fi,pre[u].se);
if(xd==k1[u]-1){
d1[u]=1;
upd(pre[u].fi,k1[u]);
}
}
for(int i=1;i<=li;i++) upd(pre[i].fi,-(kt+1));
for(auto [a,u]:vp){
if(!k2[u]) continue;
int xd=qr(pre[u].fi,pre[u].se);
if(xd==-(k2[u]+1)){
d2[u]=1;
upd(pre[u].se,-k2[u]);
}
}
for(int i=1;i<=li;i++) upd(pre[i].fi,0);
for(int i=1;i<=li;i++){
if(d1[i]) kon1[k1[i]].push_back(i);
if(d2[i]) kon2[k2[i]].push_back(i);
}
for(int v=1;v<=li;v++){
if(d1[v]){
int xdd=pod[v];
int xdd2=n-pod[v]-w[k1[v]+1];
if(xdd<xdd2 or k1[v]>=kt-1){
if(k1[v]<kt-1){
if(kon2[k1[v]+2].size()){
int tw=kon2[k1[v]+2][0];
if(przodek(v,tw)){
if(kon2[k1[v]+2].size()>1) odp={v,kon2[k1[v]+2][1]};
}else odp={v,kon2[k1[v]+2][0]};
}
}else odp={v,0};
}
}
if(d2[v]){
int xdd=pod[v];
int xdd2=n-pod[v]-w[k2[v]-1];
if(xdd>=xdd2 or k2[v]<=2){
if(k2[v]>2){
if(kon1[k2[v]-2].size()){
int tw=kon1[k2[v]-2][0];
if(przodek(v,tw)){
if(kon1[k2[v]-2].size()>1) odp={kon1[k2[v]-2][1],v};
}else odp={kon1[k2[v]-2][0],v};
}
}else odp={0,v};
}
}
}
if(odp.fi or odp.se){
if(odp.fi){
for(int i=1;i<=li;i++) kol[i]=t2[k1[odp.fi]+1];
}else{
for(int i=1;i<=li;i++) kol[i]=t2[k2[odp.se]-1];
}
if(odp.fi){
p1=k1[odp.fi];
dfs5(odp.fi,p1);
}
if(odp.se){
p2=k2[odp.se];
dfs6(odp.se,p2);
}
cout<<"Yes\n";
for(int i=1;i<=n;i++){
cout<<kol[fau[i]]<<" ";
}
cout<<"\n";
}else cout<<"No\n";
li=0,kt=0,p1=0,p2=0,odp={0,0},l=0;
for(int i=1;i<=n;i++){
d1[i]=0,d2[i]=0,pod[i]=0,dep[i]=0,kon1[i].clear(),kon2[i].clear(),graf[i].clear();
graf2[i].clear(),graf3[i].clear(),lo[i]=0,vis[i]=0,g[i]=0,fau[i]=0;
k1[i]=0,k2[i]=0,w[i]=0,t[i]=0,t2[i]=0;
}
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int tt=1;
cin>>tt;
while(tt--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 19920kb
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 1 2 2 3 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 120ms
memory: 20256kb
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 1 1 2 No Yes 1 1 No Yes 1 1 N...
result:
wrong answer ans finds an answer, but out doesn't (test case 317)