oj.uz

Submission #89156

# Submission time Handle Problem Language Result Execution time Memory
89156 2018-12-10T15:55:06 Z faustaadp Duathlon (APIO18_duathlon) C++17
23 / 100
 164 ms 35432 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,i,ta,tb,has,besar[101010],ketua[101010],b[101010];
vector<ll> v[101010];
void dfs1(ll aa,ll bb)
{
    if(ketua[aa]!=0)return;
    ketua[aa]=i;
    besar[aa]=1;
    ll ii;
    for(ii=0;ii<v[aa].size();ii++)
    {
        if(v[aa][ii]==bb)continue;
        dfs1(v[aa][ii],aa);
        besar[aa]+=besar[v[aa][ii]];
    }
}
void dfs2(ll aa,ll bb)
{
    if(b[aa])return ;
    b[aa]=1;
    ll ii,tot=0;
    vector<ll> x;
    x.pb(besar[ketua[aa]]-besar[aa]);
    for(ii=0;ii<v[aa].size();ii++)
        if(v[aa][ii]!=bb)
            x.pb(besar[v[aa][ii]]);
    for(ii=0;ii<v[aa].size();ii++)
        if(v[aa][ii]!=bb)
            dfs2(v[aa][ii],aa);
    for(ii=0;ii<x.size();ii++)
    {
  //      cout<<aa<<" "<<2<<" "<<x[ii]<<" "<<tot<<"\n";
        has+=2LL*x[ii]*tot;
        tot+=x[ii];
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>ta>>tb;
        v[ta].pb(tb);
        v[tb].pb(ta);
    }
    for(i=1;i<=n;i++)
    {
        if(besar[i]==0)
        {
            //cout<<i<<" "<<i<<"\n";
            dfs1(i,i);
            dfs2(i,i);
        }
    }
    cout<<has<<"\n";
}

Compilation message

count_triplets.cpp: In function 'void dfs1(long long int, long long int)':
count_triplets.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ii=0;ii<v[aa].size();ii++)
              ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(long long int, long long int)':
count_triplets.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ii=0;ii<v[aa].size();ii++)
              ~~^~~~~~~~~~~~~
count_triplets.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ii=0;ii<v[aa].size();ii++)
              ~~^~~~~~~~~~~~~
count_triplets.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ii=0;ii<x.size();ii++)
              ~~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 20864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20864 KB Output is correct
2 Correct 4 ms 20864 KB Output is correct
3 Correct 4 ms 20864 KB Output is correct
4 Correct 4 ms 20864 KB Output is correct
5 Correct 4 ms 20864 KB Output is correct
6 Correct 4 ms 20864 KB Output is correct
7 Correct 4 ms 20864 KB Output is correct
8 Correct 4 ms 20864 KB Output is correct
9 Correct 5 ms 20864 KB Output is correct
10 Correct 4 ms 20864 KB Output is correct
11 Correct 4 ms 20864 KB Output is correct
12 Correct 4 ms 20864 KB Output is correct
13 Correct 4 ms 20864 KB Output is correct
14 Correct 4 ms 20864 KB Output is correct
15 Correct 4 ms 20864 KB Output is correct
16 Correct 4 ms 20864 KB Output is correct
17 Correct 4 ms 20864 KB Output is correct
18 Correct 4 ms 20864 KB Output is correct
19 Correct 4 ms 20864 KB Output is correct
20 Correct 4 ms 20864 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 20864 KB Output is correct
2 Correct 138 ms 20864 KB Output is correct
3 Correct 151 ms 20864 KB Output is correct
4 Correct 78 ms 20864 KB Output is correct
5 Correct 75 ms 20864 KB Output is correct
6 Correct 104 ms 21872 KB Output is correct
7 Correct 97 ms 21872 KB Output is correct
8 Correct 104 ms 21872 KB Output is correct
9 Correct 142 ms 21872 KB Output is correct
10 Correct 101 ms 21872 KB Output is correct
11 Correct 137 ms 22004 KB Output is correct
12 Correct 102 ms 23360 KB Output is correct
13 Correct 112 ms 24608 KB Output is correct
14 Correct 123 ms 25368 KB Output is correct
15 Correct 103 ms 26108 KB Output is correct
16 Correct 54 ms 26108 KB Output is correct
17 Correct 79 ms 29508 KB Output is correct
18 Correct 84 ms 31044 KB Output is correct
19 Correct 89 ms 32440 KB Output is correct
20 Correct 84 ms 33300 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33300 KB Output is correct
2 Correct 4 ms 33300 KB Output is correct
3 Incorrect 4 ms 33300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 33300 KB Output is correct
2 Correct 132 ms 33416 KB Output is correct
3 Incorrect 164 ms 35432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -