oj.uz

Submission #52811

# Submission time Handle Problem Language Result Execution time Memory
52811 2018-06-26T20:36:58 Z FLDutchman Duathlon (APIO18_duathlon) C++14
18 / 100
 1000 ms 28344 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define MMAX 16384
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 1e5+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

int N, M;

vi adj[NMAX];

vi idx, low, color;
stack<int> comp;
vi size;
int id, c;

int findBridges(int n, int p){
    idx[n] = low[n] = id++;
    comp.push(n);
    for(int k : adj[n]) if(k != p) {
        if(idx[k] == -1) low[n] = min(low[n],  findBridges(k, n) );
        else low[n] = min(low[n], idx[k]);
    }
    if(low[n] == idx[n]) {
        size.pb(1);
        while(comp.top() != n) {
            color[comp.top()] = c;
            comp.pop();
            size[c]++;
        }
        color[comp.top()] = c;
        comp.pop();
        c++;
    }
    return low[n];
}

vi tree[NMAX];
bitset<NMAX> vis;

void buildTree(int n){
    vis[n] = 1;
    for(int k : adj[n]){
        if(color[k] != color[n]) tree[color[k]].pb(color[n]);
        if(!vis[k]) buildTree(k);
    }
}

vi subSize[NMAX];
int dfs(int n, int p){
    int sum = size[n];
    for(int i = 0; i < tree[n].size(); i++) {
        int k = tree[n][i], &s = subSize[n][i];
        if(k == p) continue;
        if(s == -1) s = dfs(k, n);
        sum += s;
    }
    //cout << n << " " << p << " " << sum << endl;
    return sum;
}

int f(int n){
    int C = size[n];
    int S = 0;
    for(int t : subSize[n]) S += t;
    int sum = 0;
    for(int t : subSize[n]) sum += t*t;
    //cout << "f " << C << " " << S << " " << sum << endl;
    return C*(C-1)*(C-2)
         + 2*(C-1)*(C-1)*S
         + C*(S*S - sum);
}

signed main(){
    fast_io();
    c = 0;
    cin >> N >> M;
    FOR(i, 0, M){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    idx.assign(N, -1); low.assign(N, INF);
    color.assign(N, -1);
    FOR(i, 0, N) if(idx[i] == -1) findBridges(i, -1);
    //FOR(i, 0, N)        cout << color[i] << endl;
    vis.reset();
    FOR(i, 0, N) if(!vis[i]) buildTree(i);

    //FOR(i, 0, c) for(int k : tree[i]) cout << i << " " << k << endl;
    FOR(i, 0, c) subSize[i].assign(tree[i].size(), -1);
    FOR(i, 0, c) dfs(i, -1);


    int sum = 0;
    FOR(i, 0, c) sum += f(i);
    cout << sum << endl;
}


/*
4 3
1 2
2 3
3 4


4 4
1 2
2 3
3 4
4 2


*/

Compilation message

count_triplets.cpp: In function 'long long int dfs(long long int, long long int)':
count_triplets.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < tree[n].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 7 ms 7484 KB Output is correct
4 Correct 7 ms 7660 KB Output is correct
5 Correct 7 ms 7660 KB Output is correct
6 Correct 8 ms 7660 KB Output is correct
7 Incorrect 9 ms 7712 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 7 ms 7484 KB Output is correct
4 Correct 7 ms 7660 KB Output is correct
5 Correct 7 ms 7660 KB Output is correct
6 Correct 8 ms 7660 KB Output is correct
7 Incorrect 9 ms 7712 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 125 ms 23400 KB Output is correct
2 Correct 153 ms 23400 KB Output is correct
3 Correct 156 ms 23400 KB Output is correct
4 Correct 182 ms 23400 KB Output is correct
5 Correct 112 ms 23400 KB Output is correct
6 Correct 149 ms 23400 KB Output is correct
7 Correct 140 ms 23400 KB Output is correct
8 Correct 155 ms 23400 KB Output is correct
9 Correct 144 ms 23400 KB Output is correct
10 Correct 171 ms 23400 KB Output is correct
11 Correct 101 ms 23400 KB Output is correct
12 Correct 83 ms 23400 KB Output is correct
13 Correct 79 ms 23400 KB Output is correct
14 Correct 79 ms 23400 KB Output is correct
15 Correct 68 ms 23400 KB Output is correct
16 Correct 103 ms 23400 KB Output is correct
17 Correct 14 ms 23400 KB Output is correct
18 Correct 17 ms 23400 KB Output is correct
19 Correct 14 ms 23400 KB Output is correct
20 Correct 16 ms 23400 KB Output is correct
21 Correct 13 ms 23400 KB Output is correct
22 Correct 16 ms 23400 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 23400 KB Output is correct
2 Correct 128 ms 23400 KB Output is correct
3 Correct 199 ms 23400 KB Output is correct
4 Correct 118 ms 23400 KB Output is correct
5 Correct 120 ms 23400 KB Output is correct
6 Correct 144 ms 28344 KB Output is correct
7 Correct 136 ms 28344 KB Output is correct
8 Correct 143 ms 28344 KB Output is correct
9 Correct 138 ms 28344 KB Output is correct
10 Correct 125 ms 28344 KB Output is correct
11 Correct 127 ms 28344 KB Output is correct
12 Correct 124 ms 28344 KB Output is correct
13 Correct 125 ms 28344 KB Output is correct
14 Correct 112 ms 28344 KB Output is correct
15 Correct 93 ms 28344 KB Output is correct
16 Correct 61 ms 28344 KB Output is correct
17 Execution timed out 1082 ms 28344 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 28344 KB Output is correct
2 Correct 8 ms 28344 KB Output is correct
3 Incorrect 8 ms 28344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 28344 KB Output is correct
2 Correct 136 ms 28344 KB Output is correct
3 Incorrect 139 ms 28344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 7 ms 7484 KB Output is correct
4 Correct 7 ms 7660 KB Output is correct
5 Correct 7 ms 7660 KB Output is correct
6 Correct 8 ms 7660 KB Output is correct
7 Incorrect 9 ms 7712 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 7 ms 7416 KB Output is correct
3 Correct 7 ms 7484 KB Output is correct
4 Correct 7 ms 7660 KB Output is correct
5 Correct 7 ms 7660 KB Output is correct
6 Correct 8 ms 7660 KB Output is correct
7 Incorrect 9 ms 7712 KB Output isn't correct
8 Halted 0 ms 0 KB -