oj.uz

Submission #396664

# Submission time Handle Problem Language Result Execution time Memory
396664 2021-04-30T14:39:21 Z SavicS Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 145 ms 16564 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,int> 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, 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, 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 3 ms 4944 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5024 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5016 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 3 ms 5016 KB Output is correct
11 Correct 3 ms 5020 KB Output is correct
12 Correct 4 ms 5020 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 4 ms 5072 KB Output is correct
15 Correct 3 ms 5068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5156 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 5300 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5296 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9884 KB Output is correct
2 Correct 51 ms 10412 KB Output is correct
3 Correct 61 ms 16540 KB Output is correct
4 Correct 43 ms 10292 KB Output is correct
5 Correct 41 ms 10208 KB Output is correct
6 Correct 145 ms 14440 KB Output is correct
7 Correct 95 ms 12612 KB Output is correct
8 Correct 86 ms 15596 KB Output is correct
9 Correct 87 ms 15744 KB Output is correct
10 Correct 76 ms 16564 KB Output is correct
11 Incorrect 80 ms 15664 KB Output isn't correct
12 Halted 0 ms 0 KB -