Submission #921137

#	Time	Username	Problem	Language	Result	Execution time	Memory
921137		ttamx	Raspad (COI17_raspad)	C++14	0 / 100	81 ms	163960 KiB

raspad

#include<bits/stdc++.h>

using namespace std;

const int N=100005;
const int M=55;
const int K=5000005;

int n,m,cnt;
vector<int> adj[K];
vector<pair<int,int>> edge;
int num[N][M],a[K];
int sz[K],hv[K],lv[K],hd[K],pa[K];
int fa[N];
long long ans;

void dfs(int u){
    sz[u]=1;
    for(auto v:adj[u]){
        lv[v]=lv[u]+1;
        pa[v]=u;
        dfs(v);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]])hv[u]=v;
    }
}

void hld(int u){
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u]);
    for(auto v:adj[u])if(v!=hv[u])hld(v);
}

int lca(int u,int v){
    while(hd[u]!=hd[v]){
        if(lv[hd[u]]<lv[hd[v]])swap(u,v);
        u=pa[hd[u]];
    }
    return lv[u]<lv[v]?u:v;
}

int fp(int u){
    return fa[u]=fa[u]==u?u:fp(fa[u]);
}

bool uni(int u,int v,int w){
    u=fp(u),v=fp(v);
    if(u==v)return false;
    fa[u]=fa[v]=++cnt;
    fa[cnt]=cnt;
    adj[cnt]={u,v};
    a[cnt]=w;
    return true;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        int tmp=0;
        for(int j=0;j<m;j++)if(s[j]=='1'){
            tmp++;
            a[++cnt]=i;
            while(j<m&&s[j]=='1')num[i][j++]=cnt;
        }
        ans+=1LL*tmp*(i+1)*(n-i);
    }
    iota(fa+1,fa+cnt+1,1);
    for(int i=n-2;i>=0;i--){
        int pu=0,pv=0;
        for(int j=0;j<m;j++){
            int u=num[i][j],v=num[i+1][j];
            if(!u||!v||(u==pu&&v==pv))continue;
            pu=u,pv=v;
            if(uni(u,v,i)){
                ans-=1LL*(i+1)*(n-i-1);
            }else{
                edge.emplace_back(u,v);
            }
        }
    }
    for(int i=cnt;i>=1;i--)if(!sz[i])dfs(i),hld(i);
    for(auto [u,v]:edge){
        int x=a[lca(u,v)];
        ans-=1LL*(x+1)*(n-a[v]);
    }
    cout << ans;
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for(auto [u,v]:edge){
      |              ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39