QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210338 | #4839. Smaller LCA | 275307894a | WA | 526ms | 103632kb | C++14 | 2.1kb | 2023-10-11 11:33:14 | 2023-10-11 11:33:14 |
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);//cerr<<i<<' '<<j<<' '<<Ls<<'\n';
if(Ls>=w){
ans[1]++;ans[Jp(Ls,i)]--;ans[Jp(Ls,j)]--;
}
Q[i].emplace_back(w,1);Q[j].emplace_back(w,1);Q[Ls].emplace_back(w,-2);
}
}
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: 0ms
memory: 31884kb
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: 526ms
memory: 103632kb
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 44999057978 44999071272 44999070275 44998337561 44998934989 44998674558 44998440838 44998314574 44998400370 44999054711 44998407705 44998546477 44999238284 44998866303 44998616992 44998391880 44998584691 44998595619 44998395742 44998998950 44998580434 44998610341 44998437862 44999301615 ...
result:
wrong answer 2nd numbers differ - expected: '44999604051', found: '44999057978'