oj.uz

Submission #176006

# Submission time Handle Problem Language Result Execution time Memory
176006 2020-01-07T14:25:37 Z Pankin Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 74 ms 11444 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.find(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.find(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 half = circle.size() / 2, cur = circle.size() / 2;
    for (ll i = 1; i <= half; 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 6 ms 4988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Incorrect 6 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 11444 KB Output isn't correct
2 Halted 0 ms 0 KB -