提出 #72825096

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define ep emplace
#define pii pair<int,int>
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mems(arr,x) memset(arr,x,sizeof(arr))
#define memc(arr1,arr2) memcpy(arr1,arr2,sizeof(arr2))
using namespace std;
const int maxn=1e5+10,inf=1e9+10;
const ll INF=1e18+10;
int n,tot;
int a[maxn];
int fa[maxn],L[maxn],R[maxn],rnk[maxn],deg[maxn];
int UL[maxn],UR[maxn],Urnk[maxn],siz[maxn],son[maxn],id[maxn<<2];
ll ans[maxn];
const int maxp=maxn<<1,maxe=maxp<<4;
struct GraphFlow{
    #define GO(x,i) for(int i=head[x],t=e[i].to,w=e[i].w,co=e[i].co;i;i=e[i].nxt,t=e[i].to,w=e[i].w,co=e[i].co)
    int S,T;
    int cnt=1;
    int head[maxp];
    struct edge{int nxt,to,w,co;}e[maxe];
    inline void add(int u,int v,int w,int co){e[++cnt]={head[u],v,w,co};head[u]=cnt;}
    inline void adde(int u,int v,int w,int co){add(u,v,w,co);add(v,u,0,-co);}
    inline void rebuild(){for(int i=0;i<=T;i++)head[i]=0;cnt=1;S=T=0;}
    ll d[maxp];
    int pre[maxp],flw[maxp];
    bool inq[maxp];
    queue<int> q;
    inline bool bfs(){
        for(int i=0;i<=T;i++)   d[i]=INF,flw[i]=inf;
        d[S]=pre[T]=0;inq[S]=true;q.ep(S);
        while(!q.empty()){
            int u=q.front();q.pop();inq[u]=false;
            GO(u,i){
                if(!w||d[t]<=d[u]+co)  continue;
                d[t]=d[u]+co;pre[t]=i;
                flw[t]=min(flw[u],w);
                if(!inq[t]){inq[t]=true;q.ep(t);}
            }
        }
        return pre[T];
    }
    inline ll SSP(){
        ll cost=0;int tim=4;
        while(tim--){
            if(!bfs())  return -1;
            cost+=flw[T]*d[T];
            for(int p=T;p!=S;p=e[pre[p]^1].to){
                e[pre[p]].w-=flw[T];e[pre[p]^1].w+=flw[T];
            }
        }
        return cost;
    }
}F;
const int maxm=maxn<<1;
struct Graph{
    #define go(tr,x,i) for(int i=tr.head[x],t=tr.e[i].to;i;i=tr.e[i].nxt,t=tr.e[i].to)
    int cnt=1;
    int head[maxn];
    struct edge{int nxt,to;}e[maxm];
    inline void add(int u,int v){e[++cnt]={head[u],v};head[u]=cnt;}
    inline void adde(int u,int v){add(u,v);add(v,u);}
    inline void rebuild(){for(int i=0;i<=n;i++)head[i]=0;cnt=1;}
}T,U;
namespace SegmentTree{
    #define ls p<<1
    #define rs p<<1|1
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define all 1,1,n
    #define setmid int mid=(l+r)>>1
    #define setpos int p,int l,int r
    pii tmp[8];int pos[maxn];
    struct tree{
        pii a[4];
        tree(){a[0]=a[1]=a[2]=a[3]=pii(inf,-1);}
        pii& operator[](int x){return a[x];}
        tree operator+(tree y){
            tree res=tree();
            merge(a,a+4,y.a,y.a+4,tmp);
            int len=0;
            for(int i=0;;i++){
                res[len++]=tmp[i];
                if(~tmp[i].se){for(int j=0;j<len-1;j++)if(res[j].se==tmp[i].se){len--;break;}}
                if(len==4)return res;
            }
            return res;
        }
    }tr[maxn<<2];
    inline void pu(int p){tr[p]=tr[ls]+tr[rs];}
    void build(setpos){if(l==r)return pos[l]=p,tr[p]=tree(),tr[p][0]=pii(a[rnk[l]],0),void();setmid;build(lson);build(rson);pu(p);}
    inline void upd(int x,int col){int p=pos[x];tr[p]=tree();tr[p][0]=pii(a[rnk[x]],col);while(p>>=1)pu(p);}
    tree query(setpos,int pl,int pr){if(l>=pl&&r<=pr)return tr[p];setmid;tree res=tree();if(pl<=mid)res=query(lson,pl,pr);if(pr>mid)res=res+query(rson,pl,pr);return res;}
    void print(setpos){if(l==r)return printf("col[%lld] = %lld\n",rnk[l],tr[p][0].se),void();setmid;print(lson);print(rson);}
}
using namespace SegmentTree;
void dfs1(int u,int ft){fa[u]=ft;L[u]=++tot;rnk[tot]=u;go(T,u,i)if(t^ft)dfs1(t,u);R[u]=tot;}
void dfs2(int u,int ft){
    son[u]=0;siz[u]=1;
    UL[u]=++tot;Urnk[tot]=u;
    go(U,u,i)if(t^ft){
        dfs2(t,u);
        if(siz[t]>siz[son[u]])  son[u]=t;
        siz[u]+=siz[t];
    }
    UR[u]=tot;
}
vector<int> clr;
void dfs3(int u,int ft,int col){
    go(U,u,i)if((t^ft)&&(t^son[u])){
        dfs3(t,u,++tot);
        for(int i=UL[t];i<=UR[t];i++)upd(L[Urnk[i]],0);
        tot--;
    }
    if(son[u])  dfs3(son[u],u,col);
    go(U,u,_)if((t^ft)&&(t^son[u])){
        tot++;
        for(int i=UL[t];i<=UR[t];i++)upd(L[Urnk[i]],tot);
    }
    {
        int cid=deg[u],cur=0;vector<int>().swap(clr);F.rebuild();
        go(T,u,_){
            cur++;
            tree res;
            if(t^fa[u]) res=query(all,L[t],R[t]);
            else{
                res=query(all,1,L[u]-1);
                if(R[u]^n)  res=res+query(all,R[u]+1,n);
            }
            for(int i=0;i<4;i++){
                int w=res[i].fi,c=res[i].se;
                if(!~c)break;
                if(!id[c])    id[c]=++cid,clr.eb(c);
                F.adde(cur,id[c],1,w);
            }
        }
        F.S=0;F.T=++cid;
        if(cid-deg[u]<4)    ans[u]=-1;
        else{
            for(int i=1;i<=cur;i++) F.adde(F.S,i,1,0);
            for(int i=cur+1;i<=cid;i++) F.adde(i,F.T,1,0);
            ans[u]=F.SSP();
        }
        deg[u]=0;for(int i:clr)id[i]=0;
    }
    upd(L[u],col);
    go(U,u,_)if((t^ft)&&(t^son[u])){
        for(int i=UL[t];i<=UR[t];i++)upd(L[Urnk[i]],col);
    }
}
void matt(){
    T.rebuild();U.rebuild();tot=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);T.adde(u,v);deg[u]++;deg[v]++;}
    for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);U.adde(u,v);}
    dfs1(1,0);tot=0;dfs2(1,0);tot=0;build(all);dfs3(1,0,++tot);
    for(int i=1;i<=n;i++)   printf("%lld ",ans[i]);puts("");
}
main(){int T;scanf("%lld",&T);while(T--)matt();}

提出情報

コンパイルエラー

./Main.cpp: In function 'void SegmentTree::print(int, int, int)':
./Main.cpp:98:54: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
   98 |     void print(setpos){if(l==r)return printf("col[%lld] = %lld\n",rnk[l],tr[p][0].se),void();setmid;print(lson);print(rson);}
      |                                                   ~~~^            ~~~~~~
      |                                                      |                 |
      |                                                      long long int     int
      |                                                   %d
./Main.cpp:98:62: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
   98 |     void print(setpos){if(l==r)return printf("col[%lld] = %lld\n",rnk[l],tr[p][0].se),void();setmid;print(lson);print(rson);}
      |                                                           ~~~^
      |                                                              |
      |                                                              long long int
      |                                                           %d
./Main.cpp: In function 'void matt()':
./Main.cpp:162:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  162 |     for(int i=1;i<=n;i++)   printf("%lld ",ans[i]);puts("");
      |     ^~~
./Main.cpp:162:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  162 |     for(int i=1;i<=n;i++)   printf("%lld ",ans[i]);puts("");
      |                                                    ^~~~
./Main.cpp: At global scope:
./Main.cpp:164:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  164 | main(){int T;scanf("%lld",&T);while(T--)matt();}
      | ^~~~
./Main.cpp: In function 'int main()':
./Main.cpp:164:24: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
  164 | main(){int T;scanf("%lld",&T);while(T--)matt();}
      |                     ~~~^  ~~
      |                        |  |
      |                        |  int*
      |                        long long int*
      |                     %d

ジャッジ結果