oj.uz

Submission #396665

# Submission time Handle Problem Language Result Execution time Memory
396665 2021-04-30T14:40:14 Z SavicS Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 156 ms 17020 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = 200005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n;

vector<int> g[maxn];

vector<int> krug;

int par[maxn];
int visited[maxn];
void dfs1(int v, int p) {
    visited[v] = 1;
    par[v] = p;
    for(auto u : g[v]) {
        if(u == p)continue;
        if(!visited[u])dfs1(u, v);
        else {
            if(visited[u] == 1) {
                int A = v;
                while(A != u) {
                    krug.pb(A);
                    A = par[A];
                }
                krug.pb(u);
            }
        }
    }
    visited[v] = 2;
}

pii dia = {0, 0};
pii ja[maxn];

pii cmb(pii X, pii Y) {
    if(X.fi == Y.fi)return {X.fi, X.se + Y.se};
    return (X.fi > Y.fi ? X : Y);
}

bool bio[maxn];
pii dfs2(int v, int p, int duz) {
    bio[v] = 1;

    pii best = {duz, 1};
    for(auto u : g[v]) {
        if(u == p || bio[u])continue;
        pii dist = dfs2(u, v, duz + 1);
        dia = cmb(dia, {best.fi + dist.fi - 2 * duz, 1ll * dist.se * best.se});
        best = cmb(best, dist);
    }

    return best;
}

pii bor[4 * maxn];
void build(int v, int tl, int tr) {
    if(tl == tr) {
        bor[v] = {ja[tl].fi - tl, ja[tl].se};
        return;
    }
    int  mid = (tl + tr) / 2;
    build(v * 2, tl, mid);
    build(v * 2 + 1, mid + 1, tr);
    bor[v] = cmb(bor[v * 2], bor[v * 2 + 1]);
}

pii kveri(int v, int tl, int tr, int l, int r) {
    if(tl > r || l > tr)return {-inf, 0};
    if(tl >= l && tr <= r)return bor[v];
    int mid = (tl + tr) / 2;
    return cmb(kveri(v * 2, tl, mid, l, r), kveri(v * 2 + 1, mid + 1, tr, l, r));
}

int main() 
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n;
    ff(i,1,n) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs1(1, -1);
    for(auto c : krug)bio[c] = 1;

    int M = sz(krug);
    ff(i,0,M - 1)ja[i] = dfs2(krug[i], -1, 0);

    int pola = M / 2;
    build(1,0,M - 1);

    ff(i,0,M - 1) {
        pii L = kveri(1,0,M - 1, max(0,i - pola), i - 1);
        pii R = kveri(1,0,M - 1, min(M - 1, i + pola - !(M&1)) + 1, M - 1);
        R.fi += M + i, L.fi += i;

        pii X = cmb(L, R);

        dia = cmb(dia, {X.fi + ja[i].fi, 1ll * X.se * ja[i].se});

    }

    cout << dia.se << endl;

    return 0;
}
/**

6
1 2
1 3
2 4
4 3
4 5
4 6

// probati bojenje sahovski ili slicno

**/

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5284 KB Output is correct
7 Correct 6 ms 5288 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8900 KB Output is correct
2 Correct 63 ms 9292 KB Output is correct
3 Correct 63 ms 17020 KB Output is correct
4 Correct 41 ms 9224 KB Output is correct
5 Correct 43 ms 9176 KB Output is correct
6 Correct 156 ms 12472 KB Output is correct
7 Correct 109 ms 11112 KB Output is correct
8 Correct 87 ms 13304 KB Output is correct
9 Correct 97 ms 13340 KB Output is correct
10 Correct 81 ms 14388 KB Output is correct
11 Correct 93 ms 13464 KB Output is correct
12 Correct 110 ms 16192 KB Output is correct