oj.uz

Submission #659427

# Submission time Handle Problem Language Result Execution time Memory
659427 2022-11-17T17:25:01 Z activedeltorre Duathlon (APIO18_duathlon) C++14
23 / 100
 184 ms 59384 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;
    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];
            suma=suma+(sz[curr]-1)*(sz[curr]-1)*subtree[k]*2;
        }
    }
    rest=numarconex[curr]-subtree[curr]-sz[curr];
    suma=suma+sz[curr]*(sz[curr]-1)*(sz[curr]-2);
    suma=suma+(sz[curr]-1)*(sz[curr]-1)*(rest)*2;
    total=numarconex[curr]-sz[curr];
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adi[curr][i];
        if(k!=parent)
        {
            suma=suma+sz[curr]*(total-subtree[k])*subtree[k];
        }
    }
    suma=suma+sz[curr]*(total-rest)*(rest);
}
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:81: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]
   81 |     for(i=0; i<adi[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp:96: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]
   96 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
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 Runtime error 16 ms 22636 KB Execution killed with signal 11
3 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 Runtime error 16 ms 22636 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 59384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11348 KB Output is correct
2 Correct 7 ms 11412 KB Output is correct
3 Correct 7 ms 11416 KB Output is correct
4 Correct 8 ms 11416 KB Output is correct
5 Correct 8 ms 11476 KB Output is correct
6 Correct 7 ms 11476 KB Output is correct
7 Correct 9 ms 11476 KB Output is correct
8 Correct 7 ms 11476 KB Output is correct
9 Correct 9 ms 11412 KB Output is correct
10 Correct 7 ms 11476 KB Output is correct
11 Correct 9 ms 11416 KB Output is correct
12 Correct 8 ms 11464 KB Output is correct
13 Correct 7 ms 11476 KB Output is correct
14 Correct 7 ms 11412 KB Output is correct
15 Correct 7 ms 11424 KB Output is correct
16 Correct 7 ms 11348 KB Output is correct
17 Correct 7 ms 11412 KB Output is correct
18 Correct 6 ms 11476 KB Output is correct
19 Correct 6 ms 11476 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 163 ms 26556 KB Output is correct
2 Correct 138 ms 27824 KB Output is correct
3 Correct 184 ms 27772 KB Output is correct
4 Correct 131 ms 27752 KB Output is correct
5 Correct 129 ms 27780 KB Output is correct
6 Correct 147 ms 30924 KB Output is correct
7 Correct 166 ms 30120 KB Output is correct
8 Correct 140 ms 29444 KB Output is correct
9 Correct 141 ms 28804 KB Output is correct
10 Correct 141 ms 27408 KB Output is correct
11 Correct 153 ms 27664 KB Output is correct
12 Correct 131 ms 27252 KB Output is correct
13 Correct 129 ms 27240 KB Output is correct
14 Correct 128 ms 26960 KB Output is correct
15 Correct 103 ms 26220 KB Output is correct
16 Correct 81 ms 24080 KB Output is correct
17 Correct 91 ms 28120 KB Output is correct
18 Correct 91 ms 28140 KB Output is correct
19 Correct 92 ms 28396 KB Output is correct
20 Correct 108 ms 28208 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 7 ms 11348 KB Output is correct
3 Runtime error 16 ms 22924 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 26592 KB Output is correct
2 Correct 126 ms 27524 KB Output is correct
3 Runtime error 152 ms 52564 KB Execution killed with signal 11
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 Runtime error 16 ms 22636 KB Execution killed with signal 11
3 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 Runtime error 16 ms 22636 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -