oj.uz

Submission #569081

# Submission time Handle Problem Language Result Execution time Memory
569081 2022-05-26T15:27:19 Z Waratpp123 Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
vector<long long> g[100010];
long long ans=0,sz[100010],n,gr[100010],cnt=0;
unordered_map<long long,long long> mp[100010];
void findsz(long long i,long long p){
    gr[i]=cnt;
    for(auto x: g[i]){
        if(x==p) continue;
        findsz(x,i);
    }
    sz[i]++;
    for(auto x: g[i]){
        if(x==p) continue;
        sz[i]+=sz[x];
    }
}
void findans(long long i,long long p,long long r){
    long long sum=sz[r]-sz[i];
    ans-=((sz[r]-sz[i])*(sz[r]-sz[i]));
    for(auto x : g[i]){
        if(x==p) continue;
        sum+=sz[x];
        ans-=(sz[x]*sz[x]);
    }
    ans+=(sum*sum);
    for(auto x : g[i]){
        if(x==p) continue;
        findans(x,i,r);
    }
}
int main(){
    long long m,u,v,i;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%lld %lld",&u,&v);
        if(mp[u][v]!=0) continue;
        mp[u][v]=mp[v][u]=1;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(i=1;i<=n;i++){
        if(gr[i]!=0) continue;
        cnt++;
        findsz(i,-1);
        findans(i,-1,i);
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%lld %lld",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 294876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 30644 KB Output is correct
2 Correct 179 ms 30540 KB Output is correct
3 Correct 189 ms 30556 KB Output is correct
4 Correct 160 ms 30576 KB Output is correct
5 Correct 157 ms 30536 KB Output is correct
6 Correct 208 ms 32580 KB Output is correct
7 Correct 177 ms 32076 KB Output is correct
8 Correct 163 ms 31708 KB Output is correct
9 Correct 175 ms 31240 KB Output is correct
10 Correct 174 ms 30640 KB Output is correct
11 Correct 161 ms 30704 KB Output is correct
12 Correct 192 ms 30540 KB Output is correct
13 Correct 173 ms 30572 KB Output is correct
14 Correct 135 ms 29692 KB Output is correct
15 Correct 125 ms 29388 KB Output is correct
16 Correct 88 ms 24000 KB Output is correct
17 Correct 140 ms 33432 KB Output is correct
18 Correct 130 ms 33372 KB Output is correct
19 Correct 141 ms 32984 KB Output is correct
20 Correct 174 ms 32856 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8304 KB Output is correct
2 Correct 6 ms 8316 KB Output is correct
3 Runtime error 614 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 30648 KB Output is correct
2 Correct 168 ms 30432 KB Output is correct
3 Runtime error 820 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 479 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -