oj.uz

Submission #176005

# Submission time Handle Problem Language Result Execution time Memory
176005 2020-01-07T14:24:59 Z Pankin Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 78 ms 10360 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<int, int>
#define all(x) x.begin(), x.end()

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

using namespace std;

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

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

mt19937 rng(1999999973);

const int N = 200000 + 50;

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

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

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

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

void dfs(int v, int p) {
    colMx[v] = 1;
    for (int i = 0; i < g[v].size(); i++) {
        int 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(int i, int 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(int 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 (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }

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

    int half = circle.size() / 2, cur = circle.size() / 2;
    for (int i = 1; i <= half; i++) {
        add(i, 0);
    }
    for (int 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(int, int)':
shymbulak.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++) {
                     ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++) {
                     ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:157:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < circle.size(); i++)
                     ~~^~~~~~~~~~~~~~~
shymbulak.cpp:164:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int 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 4 ms 4984 KB Output is correct
2 Incorrect 3 ms 5112 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 8 ms 5116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

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