oj.uz

Submission #659435

# Submission time Handle Problem Language Result Execution time Memory
659435 2022-11-17T18:01:35 Z activedeltorre Duathlon (APIO18_duathlon) C++14
31 / 100
 156 ms 29604 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
long long sef[100005];
long long sz[100005];
long long fre[100005];
long long lvl[100005];
long long best[100005];
long long parent[100005];
vector<long long >adj[100005];
vector<long long>adi[100005];
long long find (long long u)
{
    if(sef[u]==u)
    {
        return u;
    }
    return sef[u]=find(sef[u]);
}
long long merge (long long a,long long b)
{
    a=find(a);
    b=find(b);
    if(a!=b)
    {
        if(sz[a]<sz[b])
        {
            swap(a,b);
        }
        sef[b]=a;
        sz[a]=sz[a]+sz[b];
        sz[b]=0;
        return 1;
    }
    return 0;
}
struct str
{
    long long a,b,poz,folos=0;
};
str edges[200005];
long long numarconex[100005];
long long numar=0;
vector<long long>vec;
void dfs(long long curr,long long par)
{
    vec.push_back(curr);
    parent[curr]=par;
    lvl[curr]=lvl[par]+1;
    fre[curr]=1;
    best[curr]=lvl[curr];
    numar++;
    long long i,k;
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i];
        if(fre[k]==0)
        {
            dfs(k,curr);
        }
        else if(k!=par)
        {
            best[curr]=min(best[curr],lvl[k]);
        }
    }
}
bool cmp(long long a,long long b)
{
    return lvl[a]>lvl[b];
}
long long v[100005];
long long suma=0;
long long subtree[100005];
long long n;
long long total;
void dfs2(long long curr,long long parent)
{
    long long i,k,rest,temp;
    temp=0;
    for(i=0; i<adi[curr].size(); i++)
    {
        k=adi[curr][i];
        if(k!=parent)
        {
            dfs2(k,curr);
            subtree[k]=subtree[k]+sz[k];
            subtree[curr]=subtree[curr]+subtree[k];
        }
    }
    rest=numarconex[curr]-subtree[curr]-sz[curr];
    suma=suma+sz[curr]*(sz[curr]-1)*(sz[curr]-2);
    temp=temp+sz[curr]*(sz[curr]-1)*(sz[curr]-2);
    total=numarconex[curr]-sz[curr];
    suma=suma+(sz[curr]-1)*(sz[curr]-1)*(total)*2;
    temp=temp+(sz[curr]-1)*(sz[curr]-1)*(total)*2;
    for(i=0; i<adi[curr].size(); i++)
    {
        k=adi[curr][i];
        if(k!=parent)
        {
            suma=suma+sz[curr]*(total-subtree[k])*subtree[k];
            temp=temp+sz[curr]*(total-subtree[k])*subtree[k];
        }
    }
    suma=suma+sz[curr]*(total-rest)*(rest);
    temp=temp+sz[curr]*(total-rest)*(rest);
   // cout<<curr<<" "<<temp<<'\n';
}
int capitan[100005];
int main()
{
    long long i,j,k,l,a,b,m;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        sef[i]=i;
        sz[i]=1;
    }
    for(i=1; i<=m; i++)
    {
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(i=1; i<=n; i++)
    {
        if(fre[i]==0)
        {
            numar=0;
            vec.clear();
            dfs(i,0);
            capitan[i]=1;
            for(j=0; j<vec.size(); j++)
            {
                numarconex[vec[j]]=numar;
            }
        }
    }
    int cnt=0;
    for(i=1; i<=n; i++)
    {
        if(fre[i]==0)
        {
            cnt++;
        }
    }
    if(cnt!=0)
    {
        cout<<2/0;
    }
    for(i=1; i<=n; i++)
    {
        v[i]=i;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1; i<n; i++)
    {
        if(best[v[i]]<=lvl[v[i]]-1)
        {
            best[parent[v[i]]]=min(best[v[i]],best[parent[v[i]]]);
            merge(v[i],parent[v[i]]);
        }
    }
    for(i=1; i<n; i++)
    {
        a=find(v[i]);
        b=find(parent[v[i]]);
        if(a!=b && capitan[a]==0)
        {
            adi[a].push_back(b);
            adi[b].push_back(a);
        }
    }
    for(i=1; i<=n; i++)
    {
        if(capitan[i]==1)
        {
            dfs2(find(i),0);
        }
    }
    cout<<suma;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs(long long int, long long int)':
count_triplets.cpp:56:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(long long int, long long int)':
count_triplets.cpp:82:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(i=0; i<adi[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp:98:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(i=0; i<adi[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:135:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |             for(j=0; j<vec.size(); j++)
      |                      ~^~~~~~~~~~~
count_triplets.cpp:151:16: warning: division by zero [-Wdiv-by-zero]
  151 |         cout<<2/0;
      |               ~^~
count_triplets.cpp:114:19: warning: unused variable 'k' [-Wunused-variable]
  114 |     long long i,j,k,l,a,b,m;
      |                   ^
count_triplets.cpp:114:21: warning: unused variable 'l' [-Wunused-variable]
  114 |     long long i,j,k,l,a,b,m;
      |                     ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 6 ms 11188 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 5 ms 11220 KB Output is correct
7 Incorrect 5 ms 11220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 6 ms 11188 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 5 ms 11220 KB Output is correct
7 Incorrect 5 ms 11220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 29384 KB Output is correct
2 Correct 115 ms 29332 KB Output is correct
3 Correct 156 ms 27252 KB Output is correct
4 Correct 126 ms 28636 KB Output is correct
5 Correct 123 ms 25332 KB Output is correct
6 Correct 124 ms 26192 KB Output is correct
7 Correct 126 ms 24952 KB Output is correct
8 Correct 124 ms 25668 KB Output is correct
9 Correct 119 ms 24064 KB Output is correct
10 Correct 119 ms 24560 KB Output is correct
11 Correct 98 ms 23752 KB Output is correct
12 Correct 101 ms 23644 KB Output is correct
13 Correct 91 ms 23756 KB Output is correct
14 Correct 93 ms 23504 KB Output is correct
15 Correct 73 ms 23236 KB Output is correct
16 Correct 72 ms 23004 KB Output is correct
17 Correct 16 ms 18644 KB Output is correct
18 Correct 15 ms 18628 KB Output is correct
19 Correct 14 ms 18516 KB Output is correct
20 Correct 14 ms 18444 KB Output is correct
21 Correct 14 ms 18388 KB Output is correct
22 Correct 16 ms 18336 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 26524 KB Output is correct
2 Correct 121 ms 26556 KB Output is correct
3 Correct 126 ms 26528 KB Output is correct
4 Correct 123 ms 26560 KB Output is correct
5 Correct 124 ms 26560 KB Output is correct
6 Correct 134 ms 29604 KB Output is correct
7 Correct 139 ms 28932 KB Output is correct
8 Correct 136 ms 28288 KB Output is correct
9 Correct 136 ms 27496 KB Output is correct
10 Correct 123 ms 26184 KB Output is correct
11 Correct 123 ms 26468 KB Output is correct
12 Correct 125 ms 26036 KB Output is correct
13 Correct 128 ms 25892 KB Output is correct
14 Correct 115 ms 25676 KB Output is correct
15 Correct 100 ms 25196 KB Output is correct
16 Correct 77 ms 23412 KB Output is correct
17 Correct 92 ms 26816 KB Output is correct
18 Correct 92 ms 26856 KB Output is correct
19 Correct 91 ms 27108 KB Output is correct
20 Correct 96 ms 26956 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 26552 KB Output is correct
2 Correct 124 ms 26328 KB Output is correct
3 Incorrect 129 ms 25280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 6 ms 11188 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 5 ms 11220 KB Output is correct
7 Incorrect 5 ms 11220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 6 ms 11188 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 5 ms 11220 KB Output is correct
7 Incorrect 5 ms 11220 KB Output isn't correct
8 Halted 0 ms 0 KB -