oj.uz

Submission #176009

# Submission time Handle Problem Language Result Execution time Memory
176009 2020-01-07T14:34:44 Z Pankin Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 176 ms 21060 KB 
#include <bits/stdc++.h>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define con continue
#define pii pair<ll, ll>
#define all(x) x.begin(), x.end()

const ll INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const ll mod = 1000000007;
const ll P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;

vector< pair<ll, ll> > dir = {
    {
        -1, 0
    },
    {
        0, 1
    },
    {
        1, 0
    },
    {
        0, -1
    }
};

bool valid(ll x, ll y, ll n, ll m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

const ll N = 200000 + 50;

vector<ll> g[N], circle;
ll mxDown[N], pr[N], colMx[N], mxPath = -1, col = 0, n;
bool vis[N], cycled[N];

void goBack(ll v, ll root) {
    cycled[v] = true;
    circle.pb(v);
    if (v == root)
        return;
    goBack(pr[v], root);
}

void getCycle(ll v, ll p) {
    vis[v] = true;
    pr[v] = p;
    for (ll i = 0; i < g[v].size(); i++) {
        ll to = g[v][i];
        if (to == p)
            continue;
        if (!vis[to]) {
            getCycle(to, v);
            continue;
        }
        if (circle.empty())
            goBack(v, to);
    }
}

inline void updateAns(ll len, ll am) {
    if (len > mxPath) {
        mxPath = len;
        col = 0;
    }
    if (len == mxPath) {
        col += am;
    }
}

void dfs(ll v, ll p) {
    colMx[v] = 1;
    for (ll i = 0; i < g[v].size(); i++) {
        ll to = g[v][i];
        if (cycled[to] || to == p)
            continue;
        dfs(to, v);

        updateAns(mxDown[to] + 1 + mxDown[v], colMx[to] * colMx[v]);

        if (mxDown[to] + 1 > mxDown[v]) {
            mxDown[v] = mxDown[to] + 1;
            colMx[v] = 0;
        }
        if (mxDown[to] + 1 == mxDown[v]) {
            colMx[v] += colMx[to];
        }
    }
}

struct comp {
    bool operator()(const pii &a, const pii &b) const {
        return a > b;
    }
};

set<pii, comp> st;
inline void add(ll i, ll ad) {
    auto it = st.lower_bound(mp(i + ad + mxDown[circle[i]], INF));
    if (it != st.end() && it->fs == i + ad + mxDown[circle[i]]) {
        pii val = *it;
        st.erase(it);
        val.sc += colMx[circle[i]];
        st.insert(val);
    }
    else {
        st.insert(mp(i + ad + mxDown[circle[i]], colMx[circle[i]]));
    }
}

inline void del(ll i) {
    auto it = st.lower_bound(mp(i + mxDown[circle[i]], INF));
    if (it != st.end() && it->fs == i + mxDown[circle[i]]) {
        pii val = *it;
        st.erase(it);
        val.sc -= colMx[circle[i]];
        if (val.sc != 0)
            st.insert(val);
    }
}

signed main() {
    fast_io;

    cin >> n;
    for (ll i = 0; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }

    getCycle(0, -1);
    for (ll i = 0; i < circle.size(); i++)
        dfs(circle[i], -1);

    ll cur = circle.size() / 2;
    for (ll i = 1; i <= cur; i++) {
        add(i, 0);
    }
    for (ll i = 0; i < circle.size(); i++) {
        updateAns(mxDown[circle[i]] + st.begin()->fs - i, colMx[circle[i]] * st.begin()->sc);

        if (i + 1 < circle.size())
            del(i + 1);
        cur++;
        add(cur % circle.size(), circle.size() * (cur / circle.size()));
    }

    cout << col;

    return 0;
}

Compilation message

shymbulak.cpp: In function 'void getCycle(long long int, long long int)':
shymbulak.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = 0; i < g[v].size(); i++) {
                    ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs(long long int, long long int)':
shymbulak.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = 0; i < g[v].size(); i++) {
                    ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:157:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = 0; i < circle.size(); i++)
                    ~~^~~~~~~~~~~~~~~
shymbulak.cpp:164:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = 0; i < circle.size(); i++) {
                    ~~^~~~~~~~~~~~~~~
shymbulak.cpp:167:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i + 1 < circle.size())
             ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5212 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct
6 Correct 9 ms 5440 KB Output is correct
7 Correct 9 ms 5496 KB Output is correct
8 Correct 9 ms 5484 KB Output is correct
9 Correct 8 ms 5368 KB Output is correct
10 Correct 8 ms 5368 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11500 KB Output is correct
2 Correct 67 ms 12740 KB Output is correct
3 Correct 77 ms 17824 KB Output is correct
4 Correct 49 ms 12408 KB Output is correct
5 Correct 51 ms 12528 KB Output is correct
6 Correct 176 ms 19448 KB Output is correct
7 Correct 111 ms 15824 KB Output is correct
8 Correct 101 ms 20048 KB Output is correct
9 Correct 106 ms 20168 KB Output is correct
10 Correct 99 ms 21060 KB Output is correct
11 Correct 112 ms 18020 KB Output is correct
12 Correct 122 ms 18692 KB Output is correct