oj.uz

답안 #906691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906691 2024-01-14T18:07:43 Z andrei_boaca 철인 이종 경기 (APIO18_duathlon) C++17
31 / 100
 246 ms 37344 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
ll n,m,par[100005],use[100005],niv[100005],nivmin[100005];
map<pii,int> f;
vector<int> muchii[100005];
vector<int> edges[100005];
ll nrcomp;
ll comp[100005],sz[100005],nr[100005],ans;
ll total;
void dfs(int nod)
{
    use[nod]=1;
    nivmin[nod]=niv[nod];
    for(int i:muchii[nod])
    {
        if(i==par[nod])
            continue;
        if(!use[i])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            dfs(i);
            nivmin[nod]=min(nivmin[nod],nivmin[i]);
            if(niv[nod]<nivmin[i])
                f[{nod,i}]=f[{i,nod}]=1;
        }
        else
            nivmin[nod]=min(nivmin[nod],niv[i]);
    }
}
void build(ll nod)
{
    sz[nrcomp]++;
    comp[nod]=nrcomp;
    for(int i:muchii[nod])
        if(comp[i]==0&&f.count({nod,i})==0)
            build(i);
}
void initgo(ll nod)
{
    use[nod]=1;
    total+=sz[nod];
    for(int i:edges[nod])
        if(!use[i])
            initgo(i);
}
void go(ll nod)
{
    nr[nod]=sz[nod];
    vector<ll> vals;
    for(ll i:edges[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            go(i);
            vals.push_back(nr[i]);
            nr[nod]+=nr[i];
        }
    vals.push_back(total-nr[nod]);
    ll val=sz[nod]*(sz[nod]-1)*(sz[nod]-2);
    ans+=val;
    ll suma=0;
    for(ll i:vals)
    {
        ll a=2LL*sz[nod]*i*suma;
        suma+=i;
        ans+=a;
        a=((sz[nod]-1)*(sz[nod]-2)*i+(sz[nod]-1)*i)*2LL;
        ans+=a;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!use[i])
        {
            niv[i]=1;
            dfs(i);
        }
    for(int i=1;i<=n;i++)
        if(!comp[i])
        {
            nrcomp++;
            build(i);
        }
    for(auto i:f)
    {
        ll a=i.first.first;
        ll b=i.first.second;
        a=comp[a];
        b=comp[b];
        edges[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
    {
        use[i]=0;
        par[i]=0;
    }
    for(int i=1;i<=nrcomp;i++)
        if(!use[i])
        {
            total=0;
            initgo(i);
            go(i);
        }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 24148 KB Output is correct
2 Correct 52 ms 24156 KB Output is correct
3 Correct 107 ms 27392 KB Output is correct
4 Correct 85 ms 26196 KB Output is correct
5 Correct 132 ms 22984 KB Output is correct
6 Correct 149 ms 26964 KB Output is correct
7 Correct 148 ms 26104 KB Output is correct
8 Correct 151 ms 26884 KB Output is correct
9 Correct 177 ms 25056 KB Output is correct
10 Correct 104 ms 24004 KB Output is correct
11 Correct 80 ms 20700 KB Output is correct
12 Correct 106 ms 20632 KB Output is correct
13 Correct 83 ms 20564 KB Output is correct
14 Correct 67 ms 20056 KB Output is correct
15 Correct 70 ms 19540 KB Output is correct
16 Correct 54 ms 19060 KB Output is correct
17 Correct 7 ms 10588 KB Output is correct
18 Correct 8 ms 10456 KB Output is correct
19 Correct 7 ms 10588 KB Output is correct
20 Correct 7 ms 10424 KB Output is correct
21 Correct 7 ms 10588 KB Output is correct
22 Correct 7 ms 10588 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6880 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6880 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 3 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 2 ms 6888 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 2 ms 6748 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 31284 KB Output is correct
2 Correct 227 ms 30628 KB Output is correct
3 Correct 202 ms 30804 KB Output is correct
4 Correct 174 ms 30700 KB Output is correct
5 Correct 225 ms 30864 KB Output is correct
6 Correct 246 ms 37344 KB Output is correct
7 Correct 186 ms 35408 KB Output is correct
8 Correct 194 ms 34132 KB Output is correct
9 Correct 202 ms 33096 KB Output is correct
10 Correct 201 ms 30860 KB Output is correct
11 Correct 238 ms 30868 KB Output is correct
12 Correct 176 ms 30804 KB Output is correct
13 Correct 208 ms 30700 KB Output is correct
14 Correct 154 ms 29268 KB Output is correct
15 Correct 129 ms 27628 KB Output is correct
16 Correct 92 ms 22180 KB Output is correct
17 Correct 183 ms 32172 KB Output is correct
18 Correct 166 ms 32200 KB Output is correct
19 Correct 194 ms 32280 KB Output is correct
20 Correct 182 ms 31904 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6628 KB Output is correct
3 Incorrect 3 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 30812 KB Output is correct
2 Correct 191 ms 30728 KB Output is correct
3 Incorrect 184 ms 25172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Incorrect 2 ms 6492 KB Output isn't correct
8 Halted 0 ms 0 KB -