oj.uz

Submission #252716

# Submission time Handle Problem Language Result Execution time Memory
252716 2020-07-26T07:22:05 Z khangal Duathlon (APIO18_duathlon) C++14
31 / 100
 1000 ms 1048576 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long , long long > pl;
const int N=1e6+1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18 
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll sz,n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,h,a[1234567],w,x,y,z;
bool used[1234567];
vector<ll> v[1234567];
vl vec;
void dfs(ll x, ll y){
    d[x] = 1;
    used[x] = 1;
    for(auto u : v[x]){
        if(u == y) continue;
        if(used[u]){
            c[u] = 1;
            continue;
        }
        dfs(u , x);
        d[x] += d[u];
    }
}
void solve(ll x , ll y, ll sum){
    ans += 2 * (d[x] - 1) * (sum - d[x]); 
    ll res = 0;
    for(auto u : v[x]){
        if(u == y) continue;
        ans += 2 * d[u] * res;
        res += d[u];
    }
    for(auto u : v[x]){
        if(u == y) continue;
        solve(u , x, sum);
    }
}
int main(){
    cin>>n>>m;
    for(ll i = 1; i <= m; i++){
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(ll i = 1; i <= n; i++){
        if(d[i] == 0) dfs(i , -1), vec.pb(i);
    }
    for(auto i : vec){
        if(c[i]==0) solve(i , -1 , d[i]);
        else ans += d[i] * (d[i] - 1) * (d[i] - 2);
    }
    cout<<ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29312 KB Output is correct
2 Correct 17 ms 29312 KB Output is correct
3 Correct 18 ms 29312 KB Output is correct
4 Correct 22 ms 29312 KB Output is correct
5 Correct 18 ms 29312 KB Output is correct
6 Correct 17 ms 29312 KB Output is correct
7 Incorrect 18 ms 29312 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 149 ms 38008 KB Output is correct
2 Correct 144 ms 38008 KB Output is correct
3 Correct 147 ms 35704 KB Output is correct
4 Correct 153 ms 38136 KB Output is correct
5 Correct 143 ms 36216 KB Output is correct
6 Correct 151 ms 36088 KB Output is correct
7 Correct 148 ms 35576 KB Output is correct
8 Correct 147 ms 35832 KB Output is correct
9 Correct 145 ms 35064 KB Output is correct
10 Correct 149 ms 35576 KB Output is correct
11 Correct 130 ms 35576 KB Output is correct
12 Correct 122 ms 35448 KB Output is correct
13 Correct 125 ms 35576 KB Output is correct
14 Correct 117 ms 35612 KB Output is correct
15 Correct 94 ms 34932 KB Output is correct
16 Correct 88 ms 34808 KB Output is correct
17 Correct 21 ms 31352 KB Output is correct
18 Correct 21 ms 31352 KB Output is correct
19 Correct 21 ms 31224 KB Output is correct
20 Correct 21 ms 31224 KB Output is correct
21 Correct 21 ms 31224 KB Output is correct
22 Correct 21 ms 31216 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29312 KB Output is correct
2 Correct 19 ms 29440 KB Output is correct
3 Correct 19 ms 29440 KB Output is correct
4 Correct 19 ms 29440 KB Output is correct
5 Correct 18 ms 29368 KB Output is correct
6 Correct 24 ms 29440 KB Output is correct
7 Correct 24 ms 29432 KB Output is correct
8 Correct 20 ms 29440 KB Output is correct
9 Correct 19 ms 29440 KB Output is correct
10 Correct 19 ms 29440 KB Output is correct
11 Correct 19 ms 29440 KB Output is correct
12 Correct 19 ms 29440 KB Output is correct
13 Correct 19 ms 29312 KB Output is correct
14 Correct 18 ms 29432 KB Output is correct
15 Correct 20 ms 29312 KB Output is correct
16 Correct 19 ms 29440 KB Output is correct
17 Correct 19 ms 29440 KB Output is correct
18 Correct 18 ms 29440 KB Output is correct
19 Correct 19 ms 29440 KB Output is correct
20 Correct 19 ms 29440 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 33912 KB Output is correct
2 Correct 164 ms 35200 KB Output is correct
3 Correct 157 ms 35192 KB Output is correct
4 Correct 160 ms 35192 KB Output is correct
5 Correct 157 ms 35192 KB Output is correct
6 Correct 183 ms 37112 KB Output is correct
7 Correct 177 ms 36856 KB Output is correct
8 Correct 153 ms 36344 KB Output is correct
9 Correct 154 ms 35960 KB Output is correct
10 Correct 147 ms 35192 KB Output is correct
11 Correct 142 ms 35192 KB Output is correct
12 Correct 146 ms 35192 KB Output is correct
13 Correct 143 ms 35248 KB Output is correct
14 Correct 135 ms 35064 KB Output is correct
15 Correct 120 ms 34936 KB Output is correct
16 Correct 82 ms 33908 KB Output is correct
17 Correct 123 ms 35432 KB Output is correct
18 Correct 127 ms 35524 KB Output is correct
19 Correct 122 ms 35296 KB Output is correct
20 Correct 124 ms 35304 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 19 ms 29440 KB Output is correct
3 Runtime error 766 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 33912 KB Output is correct
2 Correct 156 ms 35036 KB Output is correct
3 Runtime error 1000 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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