제출 #959497

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959497		sleepntsheep	Duathlon (APIO18_duathlon)	C++17	100 / 100	45 ms	18700 KiB

count_triplets

#include<stdio.h>
#include<stdlib.h>

#define N 200005

int mini(int i,int j)
{
    return i<j?i:j;
}

typedef struct
{
    int v,nxt;
} edge;

typedef struct
{
    edge*e;
    int eo;
    int*h;
} graph;

void ginit(graph*g,int n)
{
    g->h=(int*)malloc(sizeof(g->h[0])*n);
    g->eo=0;
    g->e=(edge*)malloc(2*sizeof g->e[0]);
}

void glink(graph*g,int u,int v)
{
    int o=++g->eo;
    if(!(o&o-1))g->e=(edge*)realloc(g->e,sizeof(g->e[0])*2*o);
    g->e[o].v=v;
    g->e[o].nxt=g->h[u];
    g->h[u]=o;
}

void gbilink(graph*g,int u,int v)
{
    glink(g,u,v);
    glink(g,v,u);
}

void gclean(graph*g)
{
    free(g->e);
    free(g->h);
}

#define giter(g,u,v) for(int j=(g).h[(u)],v=(g).e[j].v;j;j=(g).e[j].nxt,v=(g).e[j].v)

int n,m;
graph g,bct;

int dfn[N],low[N],timer,id,deg[N];

int V;
static int ss[N],so=0;
void tarjan(int u,int p)
{
    ++V;

    dfn[u]=low[u]=++timer;

    ss[so++]=u;

    giter(g,u,v)
    {
        if(v == p)continue;
        if(dfn[v])
            low[u]=mini(low[u],dfn[v]);
        else
        {
            tarjan(v,u);

            if(low[v]>=dfn[u])
            {
                int square=id++,x;
                do gbilink(&bct,square,x=ss[--so]), ++deg[square]; while (x != v);
                gbilink(&bct,square,u),++deg[square];
            }

            low[u]=mini(low[u],low[v]);
        }
    }
}

int square(int u)
{
    return u >= n;
}

int round(int u)
{
    return !square(u);
}

int weight(int u)
{
    return (square(u) ? deg[u] : -1);
}

int sz[N];

long long dfs(graph*bct,int u,int p)
{
    long long z=0, npath=0;
    sz[u] = round(u);

    giter(*bct,u,v)
    {
        if(v==p)continue;
        z += dfs(bct,v,u);
        npath+=sz[u]*1ll*sz[v];
        sz[u]+=sz[v];
    }

    npath += sz[u]*1ll*(V-sz[u]);

    return z + npath * weight(u);
}

int main()
{
    scanf("%d%d",&n,&m);
    ginit(&g,n);
    for(int i=0,u,v;i<m;++i) scanf("%d%d",&u,&v),gbilink(&g,u-1,v-1);
    ginit(&bct,2*n);

    id=n;
    long long ans=0;
    for(int i=0;i<n;++i)
    {
        if(!dfn[i])
        {
            so=0;
            V=0;
            tarjan(i, i);
            ans += dfs(&bct,i,-1);
            bct.eo=0;
        }
    }

    printf("%lld",ans*2);
}

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

count_triplets.cpp: In function 'void glink(graph*, int, int)':
count_triplets.cpp:33:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   33 |     if(!(o&o-1))g->e=(edge*)realloc(g->e,sizeof(g->e[0])*2*o);
      |            ~^~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:128:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     for(int i=0,u,v;i<m;++i) scanf("%d%d",&u,&v),gbilink(&g,u-1,v-1);
      |                              ~~~~~^~~~~~~~~~~~~~

• 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