oj.uz

Submission #260916

# Submission time Handle Problem Language Result Execution time Memory
260916 2020-08-11T07:43:06 Z wiwiho Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define printv(a, b) {bool pvs = false; \
for(auto i : a){ \
    if(pvs) b << ' '; \
    b << i; pvs = true; \
} \
b << '\n';}

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

vector<vector<int>> g;
vector<ll> sz;

ll ans = 0;
void dfs(int now, int p){
    sz[now] = 1;
    for(int i : g[now]){
        if(i == p) continue;
        dfs(i, now);
        sz[now] += sz[i];
    }
}

ll r = 0;
void dfs2(int now, int p){
    vector<ll> tmp;
    ll sum = 0;
    for(int i : g[now]){
        if(i == p) continue;
        dfs2(i, now);
        sum += sz[i];
        tmp.eb(sz[i]);
    }
    sum += r - sz[now];
    tmp.eb(r - sz[now]);
    //cerr << now << "  ";
    //printv(tmp, cerr);
    for(ll i : tmp){
        ans += (sum - i) * i;
        //cerr << "test " << (sum - i) * i << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    g.resize(n + 1);
    sz.resize(n + 1);

    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }

    for(int i = 1; i <= n; i++){
        if(sz[i]) continue;
        //cerr << "test " << i << "\n";
        dfs(i, i);
        r = sz[i];
        dfs2(i, i);
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 668 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 668 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 7168 KB Output is correct
2 Correct 74 ms 7164 KB Output is correct
3 Correct 71 ms 7160 KB Output is correct
4 Correct 82 ms 7160 KB Output is correct
5 Correct 77 ms 7060 KB Output is correct
6 Correct 105 ms 12940 KB Output is correct
7 Correct 101 ms 11256 KB Output is correct
8 Correct 119 ms 10232 KB Output is correct
9 Correct 100 ms 9208 KB Output is correct
10 Correct 99 ms 7160 KB Output is correct
11 Correct 100 ms 7160 KB Output is correct
12 Correct 102 ms 7288 KB Output is correct
13 Correct 100 ms 7164 KB Output is correct
14 Correct 66 ms 7032 KB Output is correct
15 Correct 63 ms 7032 KB Output is correct
16 Correct 37 ms 6264 KB Output is correct
17 Correct 52 ms 8560 KB Output is correct
18 Correct 49 ms 8556 KB Output is correct
19 Correct 51 ms 8428 KB Output is correct
20 Correct 58 ms 8276 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 827 ms 1048580 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 88 ms 7160 KB Output is correct
2 Correct 80 ms 7032 KB Output is correct
3 Runtime error 943 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 Runtime error 668 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 668 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -