QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210350 | #4839. Smaller LCA | 275307894a | WA | 513ms | 112804kb | C++14 | 2.2kb | 2023-10-11 11:40:11 | 2023-10-11 11:40:12 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=4e5+5,M=N*4,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n;ll ans[N];
vector<int> S[N];
int Si[N],Sn[N],d[N],fa[N],Tp[N];
void dfs1(int x,int La){
Si[x]=1;d[x]=d[La]+1;fa[x]=La;
for(int i:S[x]) if(i^La) dfs1(i,x),Si[x]+=Si[i],Si[Sn[x]]<Si[i]&&(Sn[x]=i);
}
void dfs2(int x,int La){
Tp[x]=La;if(!Sn[x]) return;dfs2(Sn[x],La);for(int i:S[x]) if(i^fa[x]&&i^Sn[x]) dfs2(i,i);
}
int LCA(int x,int y){
while(Tp[x]^Tp[y]) d[Tp[x]]<d[Tp[y]]&&(swap(x,y),0),x=fa[Tp[x]];
return d[x]<d[y]?x:y;
}
int Jp(int x,int y){
while(d[fa[Tp[y]]]>d[x]) y=fa[Tp[y]];
return Tp[x]^Tp[y]?Tp[y]:Sn[x];
}
namespace BIT{
int f[N];void add(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;}
int qry(int x){int ans=0;while(x) ans+=f[x],x-=x&-x;return ans;}
}
vector<pii> Q[N];
void dfs(int x,int La){
for(auto i:Q[x]) BIT::add(i.fi,i.se);
for(int i:S[x]) if(i^La){
int w=BIT::qry(x);dfs(i,x);w=BIT::qry(x)-w;
ans[x]+=w;ans[i]-=w;
}
}
void make(int x,int La){
for(int i:S[x]) if(i^La) ans[i]+=ans[x],make(i,x);
}
void Solve(){
int i,j;scanf("%d",&n);
for(i=1;i<n;i++) {int x,y;scanf("%d%d",&x,&y);S[x].emplace_back(y);S[y].emplace_back(x);}
dfs1(1,0);dfs2(1,1);
for(i=1;i<=n;i++) {
for(j=i+1;1ll*i*j<n;j++){
int w=i*j+1,Ls=LCA(i,j),px=(i^Ls?Jp(Ls,i):0),py=(j^Ls?Jp(Ls,j):0);//cerr<<i<<' '<<j<<' '<<Ls<<'\n';
if(Ls>=w){
ans[1]++;ans[px]--;ans[py]--;
}
if(i^Ls) Q[i].emplace_back(w,1),Q[px].emplace_back(w,-1);
if(j^Ls) Q[j].emplace_back(w,1),Q[px].emplace_back(w,-1);
}
}
dfs(1,0);make(1,0);
for(i=1;i<=n;i++) printf("%lld\n",1ll*n*(n+1)/2-ans[i]);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 31576kb
input:
5 1 2 4 2 2 5 3 5
output:
15 15 15 15 14
result:
ok 5 number(s): "15 15 15 15 14"
Test #2:
score: -100
Wrong Answer
time: 513ms
memory: 112804kb
input:
300000 40632 143306 32259 40632 225153 143306 269774 225153 289668 40632 191636 269774 85717 191636 58564 191636 156509 143306 289939 40632 247103 269774 40257 40632 98149 289668 142277 143306 291616 40257 46813 225153 56324 143306 277154 142277 53903 289668 114266 32259 152231 58564 241151 152231 4...
output:
44999437117 44999538134 44999550548 44999549589 44999050067 44999421278 44999337570 44999085096 44999027893 44999083621 44999537835 44999091375 44999217363 44999285940 44999372570 44999371501 44999074871 44999250575 44999261885 44999078953 44999493067 44999246436 44999365029 44999082164 44999337122 ...
result:
wrong answer 2nd numbers differ - expected: '44999604051', found: '44999538134'