oj.uz

답안 #114972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114972 2019-06-04T08:22:12 Z mrboorger 관광지 (IZhO14_shymbulak) C++14
0 / 100
 62 ms 8824 KB 
#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair

using namespace std;

const ll inf = 1e18 + 18;
const int maxn = 200005;

int used[maxn];
bool cycle[maxn];
int depth[maxn];
pair <int, int> cc[maxn]; // {len, cnt}
vector <int> g[maxn];
int cyclesz = 0;

vector <int> path;
bool f = false;
void findcycle(int v, int pr)
{
    used[v] = 1;
    path.pb(v);
    for(int to:g[v])
    {
        if (used[to] == 0)
        {
            findcycle(to, v);
            if (f) return; //
        }
        if (used[to] == 1 && pr != to)
        {
            f = true;
            cycle[to] = true;
            cyclesz = 1;
            while(path.back() != to)
            {
                cycle[path.back()] = true;
                path.pop_back();
                cyclesz++;
            }
            return;
        }
    }
    path.pop_back();
    used[v] = 2;
    return;
}

int maxdepth;
int maxdepth2;
int cnt;
int cnt2;

void dfs(int v, int pr, int Depth)
{
    if (Depth > maxdepth2 && int(g[v].size() == 1))
    {
        maxdepth2 = Depth;
        cnt2 = 1;
    }
    else
    if (Depth == maxdepth2 && int(g[v].size() == 1))
    {
        cnt2++;
    }
    if (maxdepth2 > maxdepth && int(g[v].size() == 1))
    {
        swap(maxdepth, maxdepth2);
        swap(cnt, cnt2);
    }
    else
    if (maxdepth == Depth && int(g[v].size() == 1))
    {
        cnt++;
    }

    depth[v] = Depth;

    for(int to:g[v])
    {
        if (to != pr && !cycle[to])
        {
            dfs(to, v, Depth + 1);
        }
    }
    return;
}

main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int len = 0;
    int ans = 0; //ll
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].pb(y);
        g[y].pb(x);
    }
    findcycle(0, 0);
    for(int i = 0; i < n; i++)
    {
        if (cycle[i])
        {
            maxdepth = 0;
            maxdepth2 = 0;
            cnt = 1;
            cnt2 = 0;
            dfs(i, i, 0);
            cc[i] = {maxdepth, cnt};
            if (maxdepth + maxdepth2 > len)
            {
                len = maxdepth + maxdepth2;
                if (maxdepth2 < maxdepth)ans = cnt * cnt2 * 2;
                    else ans = cnt * (cnt - 1);
            }
            else
            if (maxdepth + maxdepth2 == len)
            {
                if (maxdepth2 < maxdepth) ans += cnt * cnt2 * 2;
                    else ans += cnt * (cnt - 1);
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        if (cycle[i])
        {
            for(int j:g[i])
            {
                if (cycle[j])
                {
                    //obhod
                    int v = j;
                    int pr = i;
                    int LEN = cc[i].F;
                    int CNT = cc[i].S;
                    int t = (cyclesz >> 1);
                    for(t; t > 0; t--)
                    {
                        LEN++;
                        int to = -1;
                        for(auto ttt:g[v])
                        {
                            if (cycle[ttt] && ttt != pr)
                            {
                                to = ttt;
                                break;
                            }
                        }
                        if (LEN + cc[to].F > len)
                        {
                            len = LEN + cc[to].F;
                            ans = CNT * cc[to].S;
                        }
                        else
                        if (LEN + cc[to].F == len)
                        {
                            ans += CNT * cc[to].S;
                        }
                    }
                }
            }
        }
    }
//    cerr << len << endl;
    cout << (ans >> 1);
    return 0;
}

Compilation message

shymbulak.cpp:94:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:158:26: warning: statement has no effect [-Wunused-value]
                     for(t; t > 0; t--)
                          ^

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Incorrect 5 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Incorrect 7 ms 5120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 8824 KB Output isn't correct
2 Halted 0 ms 0 KB -