Submission #139041

#	Time	Username	Problem	Language	Result	Execution time	Memory
139041		abacaba	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	85 ms	11436 KiB

shymbulak

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 15;
int n, d[N], pp[N], cl[N];
int fin[N], last, tin[N], tout[N];
vector <int> g[N];
set <pair<int, int> > e;
int s, t;
bool used[N], c[N], is[N];

void precalc(int v, int p = -1) {
    tin[v] = fin[v] = ++last;
    used[v] = true;
    int child = 0;
    for(int to : g[v]) {
        if(p != to) {
            if(used[to])
                fin[v] = min(fin[v], tin[to]);
            else {
                precalc(to, v);
                fin[v] = min(fin[v], fin[to]);
                if(fin[to] >= tin[v] && p != -1)
                    is[v] = true;
                ++child;
            }
        }
    }
    if(child > 1 && p == -1)
        is[v] = true;
}

bool cycle(int v) {
    cl[v] = 1;
    for(int to : g[v]) {
        if(!cl[to]) {
            pp[to] = v;
            if(cycle(to))
                return true;
        }
        else if(cl[v] == 1 && to != pp[v]) {
            c[to] = true;
            while(v != to) {
                c[v] = true;
                e.insert({min(v, pp[v]), max(v, pp[v])});
                v = pp[v];
            }
            return true;
        }
    }
    cl[v] = 2;
    return false;
}

void bfs() {
    queue <int> q;
    q.push(s);
    used[s] = true;
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int to : g[v]) {
            if(!used[to] && e.find({min(to, v), max(to, v)}) == e.end()) {
                used[to] = true;
                d[to] = d[v] + 1;
                q.push(to);
            }
        }
    }
    q.push(s);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int to : g[v]) {
            if(!used[to] && e.find({min(to, v), max(to, v)}) != e.end()) {
                used[to] = true;
                d[to] = d[v] + 1;
                q.push(to);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    precalc(1);
    memset(used, 0, sizeof(used));
    cycle(1);
    int cntc = 0;
    for(int i = 1; i <= n; ++i) {
        cntc += c[i];
        if(c[i] && is[i]) {
            s = i;
            break;
        }
    }
    if(cntc == n) {
        cout << (n + 1) << endl;
        return 0;
    }
    memset(used, 0, sizeof(used));
    bfs();
    int maxx1 = -1, maxx2 = -1, u = 0, v = 0, cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n; ++i) {
        if(c[i]) {
            if(d[i] > maxx1)
                maxx1 = d[i], u = i, cnt1 = 0;
            if(d[i] == maxx1)
                ++cnt1;
        }
        else {
            if(d[i] > maxx2)
                maxx2 = d[i], v = i, cnt2 = 0;
            if(d[i] == maxx2)
                ++cnt2;
        }
    }
    if(maxx1 + maxx1 == cntc)
        cnt1 <<= 1;
    cout << (long long)cnt1 * cnt2 << endl;
    return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:109:33: warning: variable 'u' set but not used [-Wunused-but-set-variable]
     int maxx1 = -1, maxx2 = -1, u = 0, v = 0, cnt1 = 0, cnt2 = 0;
                                 ^
shymbulak.cpp:109:40: warning: variable 'v' set but not used [-Wunused-but-set-variable]
     int maxx1 = -1, maxx2 = -1, u = 0, v = 0, cnt1 = 0, cnt2 = 0;
                                        ^
shymbulak.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
shymbulak.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50