oj.uz

Submission #37452

# Submission time Handle Problem Language Result Execution time Memory
37452 2017-12-25T14:37:21 Z nickyrio Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 159 ms 60728 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;
typedef long long Counter;
typedef int Depth;
typedef pair<Depth, Counter> DC;
int n, visited[N], inCycle[N];
vector<int> e[N], Cycle;
int maxLength;
long long cnt;
stack<int> st;
int depth[N];
DC f[N];
bool Find_Cycle(int u, int p) {
    if (visited[u]) {
        while (true) {
            int v = st.top();
            inCycle[v] = 1;
            st.pop();
            Cycle.push_back(v);
            if (u == v) return true;
        }
    }
    st.push(u);
    visited[u] = 1;
    for (int v : e[u]) if (v != p) {
        if (Find_Cycle(v, u)) return true;
    }
    visited[u] = 0;
    st.pop();
    return false;
}

void Update(DC best, DC now) {
    if (now.first + best.first == maxLength) {
        cnt += now.second * best.second;
    }
    else {
        if (now.first + best.first > maxLength) {
            maxLength = now.first + best.first;
            cnt = now.second * best.second;
        }
    }
}

DC FindMaxDepth(int u, int p) {
    // Find maxLength in each Tree with root is a vertex in cycle
    DC best = make_pair(1, 1);
    for (int v : e[u]) if (v != p && !inCycle[v]) {
        depth[v] = depth[u] + 1;
        DC now = FindMaxDepth(v, u);
        Update(best, now);
        now.first++;
        if (best.first == now.first) best.second += now.second;
        else {
            if (best.first < now.first) best = now;
        }
    }
    Update(best, DC(0, 1));
    return best;
}
map<Depth, Counter> tab;
void FindInCycle() {
    int nCycle = Cycle.size();
    int sz = nCycle / 2;
    REP(i, sz) Cycle.push_back(Cycle[i]);
    tab.insert(f[Cycle[0]]);
    FOR(i, 1, nCycle + sz - 1) {
        DC best = *tab.rbegin();
        DC now = f[Cycle[i]]; now.first += i - 1;
        Update(best, now);
        //cout << i << ':' << maxLength << ' ' << cnt << endl;
        if (i < nCycle) {
            now.first -= 2 * i - 1;
            tab[now.first] += now.second;
        }
        if (i >= sz) {
            tab[f[Cycle[i - sz]].first - (i - sz)] -= f[Cycle[i - sz]].second;
            if (tab[f[Cycle[i - sz]].first - (i - sz)] == 0) {
                tab.erase(f[Cycle[i - sz]].first - (i - sz));
            }
        }
    }
}

int main() {
//    freopen(taskname".inp","r",stdin);
//    freopen(taskname".out","w",stdout);
    IO;
    cin >> n;
    FOR(i, 1, n) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    Find_Cycle(1, -1);
    maxLength = 0;
    cnt = 0;
    for (int u : Cycle) {
        f[u] = FindMaxDepth(u, -1);
        //cout << f[u].first << ' ' << f[u].second << endl;
    }
    FindInCycle();
    cout << cnt;return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 53016 KB Output is correct
2 Correct 9 ms 53016 KB Output is correct
3 Correct 3 ms 53016 KB Output is correct
4 Correct 6 ms 53016 KB Output is correct
5 Correct 6 ms 53148 KB Output is correct
6 Correct 9 ms 53148 KB Output is correct
7 Correct 3 ms 53148 KB Output is correct
8 Correct 9 ms 53148 KB Output is correct
9 Correct 6 ms 53148 KB Output is correct
10 Correct 9 ms 53148 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 55920 KB Output is correct
2 Correct 79 ms 56316 KB Output is correct
3 Correct 56 ms 60728 KB Output is correct
4 Correct 49 ms 56184 KB Output is correct
5 Correct 43 ms 56184 KB Output is correct
6 Correct 159 ms 58560 KB Output is correct
7 Correct 109 ms 57636 KB Output is correct
8 Correct 99 ms 59352 KB Output is correct
9 Correct 93 ms 59484 KB Output is correct
10 Correct 103 ms 59936 KB Output is correct
11 Correct 139 ms 59984 KB Output is correct
12 Correct 113 ms 60248 KB Output is correct