結果

問題 No.317 辺の追加
ユーザー vjudge1
提出日時 2025-01-19 12:23:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,014 bytes
コンパイル時間 1,528 ms
コンパイル使用メモリ 162,984 KB
実行使用メモリ 6,016 KB
最終ジャッジ日時 2025-01-19 12:23:24
合計ジャッジ時間 9,918 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define ll long long
ll read(){
    ll x=1,y=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') x=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        y=(y<<1)+(y<<3)+(c^48);
        c=getchar();
    }
    return x*y;
}
void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
using namespace std;
const int N=400010;
ll n1,m1;
ll n,m;
ll d[N],f[N],ans;
ll q[N],l,r;
ll fa[N],siz[N];
ll num[N];
ll fnd(ll x){
    if(fa[x]==x) return x;
    return fa[x]=fnd(fa[x]);
}
int main(){
    cin>>n1>>m1;
    for(int i=1;i<=n1;i++) fa[i]=i,siz[i]=1;
    for(int i=1;i<=m1;i++){
        ll x,y;
        cin>>x>>y;
        ll fx=fnd(x),fy=fnd(y);
        if(fx!=fy){
            fa[fy]=fx;
            siz[fx]+=siz[fy];
            siz[fy]=0;
        }
    }
    for(int i=1;i<=n1;i++){
        if(siz[i]>0){
            num[siz[i]]++;
        }
    }
    for(int i=n;i>=0;i--){
        if(siz[i]>0){
            n=i;
            break;
        }
    }
    
    m=n1;
    for(int i=1;i<=m;i++) d[i]=-0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++){
        ll x,y,z;
        y=i;z=-1;x=num[i];
        // cin>>y>>z>>x;
//         memset(f,0,sizeof(f));
        for(int j=1;j<=m*2;j++){
            f[j]=-0x3f3f3f3f3f3f3f;
        }
        f[0]=0;
        for(int j=0;j<y;j++){
            ll w=(m-j)/y+1;
            l=1;r=0;
            for(int k=0;k<=w&&k*y+j<=m;k++){
                // if(k*y+j==0) continue;
                ll u=k*y+j;
                while(l<=r&&k-q[l]>x) l++;
                
                if(l<=r){
                    f[u]=max(f[u],d[q[l]*y+j]-q[l]*z+k*z);
                }
                
                while(l<=r&&d[q[r]*y+j]-q[r]*z<=d[u]-k*z) r--;
                
                q[++r]=k;
            }
        }
        for(int j=1;j<=m;j++){
            d[j]=max(d[j],f[j]);
//            f[j]=-0x3f3f3f3f3f3f3f3f;
            // cout<<f[j]<<" ";
        }
        // cout<<endl;
    }
    for(int i=1;i<=m;i++){
        if(d[i]<-2*n) cout<<-1<<endl;
        else cout<<-d[i]-1<<endl;
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0