Lates @ 2020-03-11 13:47:23
最后一个subtask RE+TLE
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int read(){
register int x=0,f=0,ch=getchar();
while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
return f?-x:x;
}
const int MAX=10005,MAXN=10000005;
struct E{
int e,next,w;
}e[MAX<<1];
int cnt=1,head[MAX<<1];
inline void add(int u,int v,int w){
e[cnt]=(E){v,head[u],w};
head[u]=cnt++;
}
int siz[MAX],f[MAX],vis[MAX],rt,S;
int dis[MAX],tot,res[MAXN];
inline int _max(int a,int b){
return a>b?a:b;
}
void Get_root(int x,int fa){
siz[x]=1;f[x]=0;
for(register int i=head[x];i;i=e[i].next){
if(e[i].e!=fa&&!vis[e[i].e]){
Get_root(e[i].e,x);
siz[x]+=siz[e[i].e];
f[x]=_max(f[x],siz[e[i].e]);
}
}
f[x]=_max(f[x],S-siz[x]);
if(f[x]<f[rt])rt=x;
}
void Get_dis(int x,int fa,int l){
dis[++tot]=l;
for(register int i=head[x];i;i=e[i].next){
if(e[i].e!=fa&&!vis[e[i].e])Get_dis(e[i].e,x,l+e[i].w);
}
}
inline void calc(int x,int l,int v){
tot=0;
Get_dis(x,0,l);
for(register int i=1;i<=tot;++i)for(register int j=1;j<=tot;++j)res[dis[i]+dis[j]]+=v;
}
void solve(int x){
vis[x]=1;
calc(x,0,1);
for(register int i=head[x];i;i=e[i].next){
if(!vis[e[i].e]){
calc(e[i].e,e[i].w,-1);
rt=0;S=siz[e[i].e];
Get_root(e[i].e,0);
solve(rt);
}
}
}
int n,m,s,t,w;
signed main(){
n=read(),m=read();
for(register int i=1;i<n;++i){
s=read(),t=read(),w=read();
add(s,t,w);add(t,s,w);
}
rt=0;f[0]=S=n;
Get_root(1,0);
solve(rt);
for(register int i=1;i<=m;++i){
w=read();
printf("%s\n",res[w]?"AYE":"NAY");
}
return 0;
}by dbxxx @ 2020-03-11 13:47:57
qndmx
by QiFeng233 @ 2020-03-11 13:57:01
QNDMX
by chen_03 @ 2020-03-11 14:22:44
QNDMX
by chen_03 @ 2020-03-11 14:28:35
by Aw顿顿 @ 2020-03-11 14:38:04
by Lates @ 2020-03-11 14:38:17
@chen_03 Orz c03
by yama是女孩子 @ 2020-03-11 14:41:50
@Lates 总觉得您的clac似乎常数大了点
试试双指针
by yama是女孩子 @ 2020-03-11 14:42:45
RE窝解释不清楚
by Smile_Cindy @ 2020-03-11 14:43:18
@Lates 你这样对每条路径都算一遍不TLE才怪
我的代码放这了，自己研究吧
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAX_N=10005;
struct Edge
{
int v,w,nxt;
Edge(){}
Edge(int _v,int _w,int _nxt)
{
v=_v;
w=_w;
nxt=_nxt;
}
}E[MAX_N<<1];
int n,T;
int head[MAX_N];
int mx[MAX_N];
int siz[MAX_N];
bool used[MAX_N];
int q[MAX_N];
int ans[MAX_N];
int cnt=0;
void add_edge(int u,int v,int w)
{
E[cnt]=Edge(v,w,head[u]);
head[u]=cnt++;
}
void dfs_size(int v,int last)
{
siz[v]=1;
mx[v]=0;
for(int i=head[v];i!=-1;i=E[i].nxt)
{
int u=E[i].v;
if(u==last || used[u])continue;
dfs_size(u,v);
siz[v]+=siz[u];
mx[v]=max(mx[v],siz[u]);
}
}
int mi=1e9,rt=0;
void dfs_root(int idx,int v,int last)
{
mx[v]=max(mx[v],siz[idx]-siz[v]);
if(mx[v]<mi)
{
mi=mx[v];
rt=v;
}
for(int i=head[v];i!=-1;i=E[i].nxt)
{
int u=E[i].v;
if(u==last || used[u])continue;
dfs_root(idx,u,v);
}
}
int dist[MAX_N];
int top=0;
void dfs_dist(int v,int last,int dis)
{
dist[top++]=dis;
for(int i=head[v];i!=-1;i=E[i].nxt)
{
int u=E[i].v,w=E[i].w;
if(u==last || used[u])continue;
dfs_dist(u,v,dis+w);
}
}
const int MAX_L=1e7+5;
int mp[MAX_L];
void counting(int v,int dis,int flag)
{
top=0;
dfs_dist(v,0,dis);
int ret=0;
for(int i=0;i<top;i++)
{
for(int j=0;j<T;j++)
{
if(q[j]>=dist[i])ans[j]+=flag*mp[q[j]-dist[i]];
}
if(dist[i]<MAX_L)mp[dist[i]]++;
}
for(int i=0;i<top;i++)if(dist[i]<MAX_L)mp[dist[i]]--;
}
void solve(int v)
{
dfs_size(v,0);
mi=n;
dfs_root(v,v,0);
used[rt]=true;
counting(rt,0,1);
for(int i=head[rt];i!=-1;i=E[i].nxt)
{
int u=E[i].v,w=E[i].w;
if(used[u])continue;
counting(u,w,-1);
solve(u);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(head,-1,sizeof(head));
cnt=0;
cin>>n>>T;
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,w);
}
for(int i=0;i<T;i++)
{
int x;
cin>>x;
q[i]=x;
}
solve(1);
for(int i=0;i<T;i++)
{
if(ans[i])cout<<"AYE"<<endl;
else cout<<"NAY"<<endl;
}
return 0;
} by yama是女孩子 @ 2020-03-11 14:44:52
@Lates 我的代码给您参考一下QwQ
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std ;
const int MAXN = 1e4 + 10 , INF = 0x3f3f3f3f ;
int n , m , size[MAXN] , maxsize[MAXN] , cnt , r , rt , minn = INF ;
int dis[MAXN] , tmp[MAXN] , ans[MAXN] , q[MAXN] ;
bool vis[MAXN] ;
struct edge {
int to , cost ;
edge (int v = 0 , int w = 0) {to = v ; cost = w ;}
} ;
vector <edge> G[MAXN] ;
int R() {
int x = 0 ; char ch = getchar () ; bool f = 0 ;
for (; ch < 48 || ch > 57 ; ch = getchar ()) if (ch == '-') f = 1 ;
for (; ch >= 48 && ch <= 57 ; ch = getchar ()) x = (x << 1) + (x << 3) + (ch ^ 48) ;
return f ? -x : x ;
}
void findrt (int x , int fa) {
size[x] = 1 ; maxsize[x] = 0 ;
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i].to ;
if (v == fa || vis[v]) continue ;
findrt (v , x) ;
size[x] += size[v] ;
if (size[v] > maxsize[x])
maxsize[x] = size[v] ;
}
if (cnt - size[x] > maxsize[x])
maxsize[x] = cnt - size[x] ;
if (maxsize[x] < minn) {
minn = maxsize[x] ;
rt = x ;
}
}
void getdis (int x , int fa) {
tmp[++r] = dis[x] ;
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i].to , w = G[x][i].cost ;
if (v == fa || vis[v]) continue ;
dis[v] = dis[x] + w ;
getdis (v , x) ;
}
}
void query (int x , int w , int type) {
dis[x] = w ; r = 0 ;
getdis (x , 0) ;
sort (tmp + 1 , tmp + r + 1) ;
int l = 1 , tt = r ;
for (int i = 1 ; i <= m ; i++) {
l = 1 ; r = tt ;
while (l < r) {
if (tmp[l] + tmp[r] <= q[i]) ans[i] += type * (r - l) , l++ ;
else r-- ;
}
l = 1 ; r = tt ;
while (l < r) {
if (tmp[l] + tmp[r] < q[i]) ans[i] -= type * (r - l) , l++ ;
else r-- ;
}
}
}
void divide (int x) {
vis[x] = 1 ;
query (x , 0 , 1) ;
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i].to , w = G[x][i].cost ;
if (vis[v]) continue ;
query (v , w , -1) ;
minn = INF ; rt = 0 ;
cnt = size[v] ;
findrt (v , 0) ;
divide (rt) ;
}
}
int main() {
n = R() ; m = R() ;
for (int i = 1 ; i < n ; i++) {
int u = R() , v = R() , w = R() ;
G[u].push_back (edge (v , w)) ;
G[v].push_back (edge (u , w)) ;
}
for (int i = 1 ; i <= m ; i++) q[i] = R() ;
cnt = n ;
findrt (1 , 0) ;
divide (rt) ;
for (int i = 1 ; i <= m ; i++) {
if (ans[i]) printf ("AYE\n") ;
else printf ("NAY\n") ;
}
return 0 ;
}