oj.uz

Submission #487269

# Submission time Handle Problem Language Result Execution time Memory
487269 2021-11-15T02:16:34 Z SirCovidThe19th Shymbulak (IZhO14_shymbulak) C++17
100 / 100
 225 ms 15872 KB 
#include <bits/stdc++.h>
using namespace std;

#define pil pair<int, long long>
#define f first
#define s second

const int mx = 2e5 + 5;

int n, cycA, cycB, par[mx]; bool vis[mx], inCyc[mx]; pil ans; vector<int> adj[mx];

pil comb(pil A, pil B){ 
    if (A.f > B.f) B = A;
    else if (A.f == B.f) B.s += A.s;
    return B;
}
void getcyc(int u){
    vis[u] = 1; 
    for (int v : adj[u]) if (v != par[u]){ 
        if (vis[v]) tie(cycA, cycB) = {u, v};
        else par[v] = u, getcyc(v);
    }
}
pil dfs(int u, int p){
    pil bst = {0, 1};
    for (int v : adj[u]) if (v != p and !inCyc[v]){
        pil tmp = dfs(v, u); tmp.f++;
        pil pth = {tmp.f + bst.f, bst.s * tmp.s};
        ans = comb(pth, ans);
        bst = comb(tmp, bst);
    }
    return bst;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        int a, b; cin >> a >> b; 
        adj[a].push_back(b); adj[b].push_back(a);
    }    
    getcyc(1); vector<int> cyc;
    while (cycB != par[cycA]){
        inCyc[cycB] = 1; cyc.push_back(cycB); 
        cycB = par[cycB];
    }
    vector<pil> store; map<int, long long> window; pil bstL = {0, 0};
    for (int i = 0, l = -(cyc.size() / 2); i < cyc.size(); i++, l++){
        if (l >= 0){
            window[store[l].f - l] -= store[l].s;
            if (!window[store[l].f - l]) window.erase(store[l].f - l);
        }
        pil mxD = dfs(cyc[i], 0); store.push_back(mxD);
        if (window.size()){
            pil bstW = *prev(window.end());
            ans = comb({bstW.f + mxD.f + i, bstW.s * mxD.s}, ans);
        }
        ans = comb({bstL.f + mxD.f - i, bstL.s * mxD.s}, ans);
        if (l >= 0){
            pil mid = store[l]; 
            if (cyc.size() % 2 == 0) mid.s *= 2; //2 paths
            ans = comb({mid.f + mxD.f + (i - l), mid.s * mxD.s}, ans);
        }
        window[mxD.f - i] += mxD.s;
        if (l >= 0) bstL = comb({store[l].f + cyc.size() + l, store[l].s}, bstL);
    }
    cout<<ans.s<<endl;
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:47:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0, l = -(cyc.size() / 2); i < cyc.size(); i++, l++){
      |                                            ~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 5 ms 5132 KB Output is correct
6 Correct 5 ms 5156 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5220 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 75 ms 9424 KB Output is correct
2 Correct 74 ms 9988 KB Output is correct
3 Correct 79 ms 15232 KB Output is correct
4 Correct 116 ms 9920 KB Output is correct
5 Correct 67 ms 9892 KB Output is correct
6 Correct 225 ms 13704 KB Output is correct
7 Correct 120 ms 12104 KB Output is correct
8 Correct 142 ms 15084 KB Output is correct
9 Correct 141 ms 15096 KB Output is correct
10 Correct 136 ms 15872 KB Output is correct
11 Correct 134 ms 14884 KB Output is correct
12 Correct 137 ms 15392 KB Output is correct