oj.uz

Submission #659451

# Submission time Handle Problem Language Result Execution time Memory
659451 2022-11-17T19:37:18 Z activedeltorre Duathlon (APIO18_duathlon) C++14
31 / 100
 171 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]-sz[curr]-subtree[curr];
    for(i=0; i<adi[curr].size(); i++)
    {
        k=adi[curr][i];
        if(k!=parent)
        {
            suma=suma-sz[curr]*(subtree[k])*(subtree[k]-1);
        }
    }
    suma=suma-sz[curr]*(rest)*(rest-1);
   // 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;
            }
        }
    }
    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)
        {
            suma=suma+numarconex[i]*(numarconex[i]-1)*(numarconex[i]-2);
            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:93: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]
   93 |     for(i=0; i<adi[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp:80:24: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
   80 |     long long i,k,rest,temp;
      |                        ^~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:128: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]
  128 |             for(j=0; j<vec.size(); j++)
      |                      ~^~~~~~~~~~~
count_triplets.cpp:107:19: warning: unused variable 'k' [-Wunused-variable]
  107 |     long long i,j,k,l,a,b,m;
      |                   ^
count_triplets.cpp:107:21: warning: unused variable 'l' [-Wunused-variable]
  107 |     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 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11220 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 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 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11220 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 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 135 ms 29296 KB Output is correct
2 Correct 124 ms 29392 KB Output is correct
3 Correct 171 ms 27200 KB Output is correct
4 Correct 131 ms 28744 KB Output is correct
5 Correct 128 ms 25268 KB Output is correct
6 Correct 131 ms 26204 KB Output is correct
7 Correct 155 ms 25000 KB Output is correct
8 Correct 137 ms 25848 KB Output is correct
9 Correct 133 ms 24224 KB Output is correct
10 Correct 125 ms 24600 KB Output is correct
11 Correct 114 ms 23804 KB Output is correct
12 Correct 115 ms 23600 KB Output is correct
13 Correct 94 ms 23760 KB Output is correct
14 Correct 92 ms 23580 KB Output is correct
15 Correct 76 ms 23244 KB Output is correct
16 Correct 74 ms 22996 KB Output is correct
17 Correct 14 ms 18564 KB Output is correct
18 Correct 13 ms 18572 KB Output is correct
19 Correct 14 ms 18516 KB Output is correct
20 Correct 14 ms 18516 KB Output is correct
21 Correct 14 ms 18440 KB Output is correct
22 Correct 14 ms 18420 KB Output is correct

Subtask #4
10.0 / 10.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 Correct 6 ms 11348 KB Output is correct
4 Correct 7 ms 11400 KB Output is correct
5 Correct 6 ms 11476 KB Output is correct
6 Correct 7 ms 11484 KB Output is correct
7 Correct 6 ms 11476 KB Output is correct
8 Correct 6 ms 11476 KB Output is correct
9 Correct 7 ms 11428 KB Output is correct
10 Correct 6 ms 11348 KB Output is correct
11 Correct 6 ms 11440 KB Output is correct
12 Correct 7 ms 11348 KB Output is correct
13 Correct 7 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 5 ms 11348 KB Output is correct
17 Correct 6 ms 11368 KB Output is correct
18 Correct 6 ms 11476 KB Output is correct
19 Correct 6 ms 11400 KB Output is correct
20 Correct 6 ms 11476 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 26456 KB Output is correct
2 Correct 128 ms 26608 KB Output is correct
3 Correct 123 ms 26488 KB Output is correct
4 Correct 162 ms 26544 KB Output is correct
5 Correct 118 ms 26560 KB Output is correct
6 Correct 135 ms 29604 KB Output is correct
7 Correct 139 ms 28924 KB Output is correct
8 Correct 140 ms 28200 KB Output is correct
9 Correct 129 ms 27624 KB Output is correct
10 Correct 120 ms 26140 KB Output is correct
11 Correct 131 ms 26476 KB Output is correct
12 Correct 130 ms 25904 KB Output is correct
13 Correct 126 ms 26056 KB Output is correct
14 Correct 116 ms 25640 KB Output is correct
15 Correct 117 ms 25192 KB Output is correct
16 Correct 77 ms 23420 KB Output is correct
17 Correct 85 ms 26816 KB Output is correct
18 Correct 94 ms 26932 KB Output is correct
19 Correct 93 ms 27120 KB Output is correct
20 Correct 117 ms 26912 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 26528 KB Output is correct
2 Correct 129 ms 26276 KB Output is correct
3 Incorrect 132 ms 25236 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 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11220 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 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 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11220 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Incorrect 5 ms 11220 KB Output isn't correct
8 Halted 0 ms 0 KB -