oj.uz

Submission #659446

# Submission time Handle Problem Language Result Execution time Memory
659446 2022-11-17T19:22:49 Z activedeltorre Duathlon (APIO18_duathlon) C++14
31 / 100
 146 ms 29512 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]-1)*subtree[k]*2;
        }
    }
    suma=suma-sz[curr]*(rest)*(rest-1);
    suma=suma-(sz[curr]-1)*rest*2;
   // 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)
        {
            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:130: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]
  130 |             for(j=0; j<vec.size(); j++)
      |                      ~^~~~~~~~~~~
count_triplets.cpp:146:16: warning: division by zero [-Wdiv-by-zero]
  146 |         cout<<2/0;
      |               ~^~
count_triplets.cpp:109:19: warning: unused variable 'k' [-Wunused-variable]
  109 |     long long i,j,k,l,a,b,m;
      |                   ^
count_triplets.cpp:109:21: warning: unused variable 'l' [-Wunused-variable]
  109 |     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 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 6 ms 11308 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Incorrect 6 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 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 6 ms 11308 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Incorrect 6 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 139 ms 29304 KB Output is correct
2 Correct 139 ms 29332 KB Output is correct
3 Correct 144 ms 27232 KB Output is correct
4 Correct 132 ms 28580 KB Output is correct
5 Correct 131 ms 25304 KB Output is correct
6 Correct 134 ms 26124 KB Output is correct
7 Correct 135 ms 24940 KB Output is correct
8 Correct 132 ms 25780 KB Output is correct
9 Correct 135 ms 24228 KB Output is correct
10 Correct 130 ms 24604 KB Output is correct
11 Correct 105 ms 23820 KB Output is correct
12 Correct 103 ms 23644 KB Output is correct
13 Correct 98 ms 23824 KB Output is correct
14 Correct 107 ms 23680 KB Output is correct
15 Correct 76 ms 23324 KB Output is correct
16 Correct 80 ms 22984 KB Output is correct
17 Correct 14 ms 18492 KB Output is correct
18 Correct 14 ms 18516 KB Output is correct
19 Correct 15 ms 18440 KB Output is correct
20 Correct 14 ms 18532 KB Output is correct
21 Correct 14 ms 18388 KB Output is correct
22 Correct 14 ms 18312 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 8 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 6 ms 11476 KB Output is correct
6 Correct 7 ms 11476 KB Output is correct
7 Correct 6 ms 11476 KB Output is correct
8 Correct 7 ms 11484 KB Output is correct
9 Correct 7 ms 11476 KB Output is correct
10 Correct 6 ms 11348 KB Output is correct
11 Correct 6 ms 11392 KB Output is correct
12 Correct 7 ms 11348 KB Output is correct
13 Correct 6 ms 11460 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 7 ms 11348 KB Output is correct
18 Correct 6 ms 11460 KB Output is correct
19 Correct 6 ms 11472 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 146 ms 26564 KB Output is correct
2 Correct 134 ms 26632 KB Output is correct
3 Correct 127 ms 26480 KB Output is correct
4 Correct 134 ms 26520 KB Output is correct
5 Correct 124 ms 26476 KB Output is correct
6 Correct 137 ms 29512 KB Output is correct
7 Correct 137 ms 28952 KB Output is correct
8 Correct 133 ms 28256 KB Output is correct
9 Correct 128 ms 27624 KB Output is correct
10 Correct 119 ms 26176 KB Output is correct
11 Correct 124 ms 26444 KB Output is correct
12 Correct 130 ms 25956 KB Output is correct
13 Correct 120 ms 25912 KB Output is correct
14 Correct 120 ms 25648 KB Output is correct
15 Correct 106 ms 25252 KB Output is correct
16 Correct 69 ms 23468 KB Output is correct
17 Correct 92 ms 26848 KB Output is correct
18 Correct 89 ms 26872 KB Output is correct
19 Correct 89 ms 27096 KB Output is correct
20 Correct 94 ms 26876 KB Output is correct

Subtask #6
0 / 15.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 Incorrect 7 ms 11348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 26532 KB Output is correct
2 Correct 121 ms 26232 KB Output is correct
3 Incorrect 137 ms 25320 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 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 6 ms 11308 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Incorrect 6 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 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 6 ms 11308 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Incorrect 6 ms 11220 KB Output isn't correct
8 Halted 0 ms 0 KB -