제출 #54047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54047		Bodo171	철인 이종 경기 (APIO18_duathlon)	C++14	100 / 100	486 ms	69720 KiB

count_triplets

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=300005;
vector <pair<int,int> > v[nmax];
vector<int> agatat[nmax],ad[nmax],li[nmax],vec[nmax];
long long ans;
long long sum[nmax],w[nmax];
int a[nmax],b[nmax],st[nmax],lev[nmax],low[nmax],unic[nmax],rada[nmax],ap[nmax],tt[nmax],L[nmax],gr[nmax];
int n,m,i,j,bcc,u,Xul;
void chestie(int x)
{
    if(unic[x]&&unic[x]!=bcc) unic[x]=-1;
    else unic[x]=bcc;
}
void mark(int P)
{
    li[bcc].push_back(a[st[u]]);
    li[bcc].push_back(b[st[u]]);
    chestie(a[st[u]]);
    chestie(b[st[u]]);
    while(!agatat[u].empty())
    {
        ad[n+bcc].push_back(agatat[u].back());
        ad[agatat[u].back()].push_back(n+bcc);
        agatat[u].pop_back();
    }
    if(st[u]==P)
    {
        u--;
        agatat[u].push_back(Xul);
        return;
    }
    u--;
    mark(P);
}
void dfs(int x)
{
    int nod=0;
    low[x]=lev[x];
    for(int i=0;i<v[x].size();i++)
        if(!lev[v[x][i].first])
    {
        nod=v[x][i].first;st[++u]=v[x][i].second;
        lev[nod]=lev[x]+1;
        dfs(nod);
        if(low[nod]<low[x]) low[x]=low[nod];
        if(low[nod]>=lev[x])
        {
            bcc++;
            ad[x].push_back(n+bcc);
            ad[n+bcc].push_back(x);
            Xul=x;
            mark(v[x][i].second);
        }
    }
    else low[x]=min(low[x],lev[v[x][i].first]);
}
void defeseu(int x)
{
    int nod=0;
    if(x<=n){sum[x]=1LL*L[x];w[x]=1;}
    for(int i=0;i<vec[x].size();i++)
    {
        nod=vec[x][i];
        if(!tt[nod])
        {
            tt[nod]=x;
            L[nod]=L[x]+gr[nod];
            defeseu(nod);
            ans+=2LL*(1LL*sum[nod]*w[x]+1LL*sum[x]*w[nod]-1LL*w[x]*w[nod]*L[tt[x]]-1LL*w[x]*w[nod]*L[x]);
            sum[x]+=1LL*sum[nod];
            w[x]+=w[nod];
        }
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
        v[a[i]].push_back({b[i],i});
        v[b[i]].push_back({a[i],i});
    }
    for(int rr=1;rr<=n;rr++)
        if(!lev[rr])
    {
        rada[rr]=1;
        lev[rr]=1;
        dfs(rr);
    }
    for(i=1;i<=n;i++)
        if(rada[i]==0&&unic[i]!=-1)
    {
        ad[n+unic[i]].push_back(i);
        ad[i].push_back(unic[i]+n);
    }
    for(i=1;i<=n+bcc;i++)
    {
        for(j=0;j<ad[i].size();j++)
            ap[ad[i][j]]=1;
        for(j=0;j<ad[i].size();j++)
            if(ap[ad[i][j]])
              ap[ad[i][j]]=0,vec[i].push_back(ad[i][j]);
        if(i>n) gr[i]=vec[i].size()-1;
    }
    //O(n) pana aici
    for(int rr=1;rr<=n;rr++)
        if(!tt[rr])
    {
        tt[rr]=n+bcc+1;
        defeseu(rr);
        ans-=1LL*w[rr]*(w[rr]-1);
    }
    //brutulica aici
    cout<<ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void defeseu(int)':
count_triplets.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<vec[x].size();i++)
                 ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<ad[i].size();j++)
                 ~^~~~~~~~~~~~~
count_triplets.cpp:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<ad[i].size();j++)
                 ~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10