oj.uz

답안 #114996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114996 2019-06-04T10:45:54 Z mrboorger 관광지 (IZhO14_shymbulak) C++14
50 / 100
 1500 ms 14068 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];
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 len = 0;
ll ans = 0; //ll

pair <int, int> dfs(int v, int pr)
{
    vector <pair <int, ll>> vc;
    vc.pb({0, 1});
    for(int to:g[v])
    {
        if (to != pr && !cycle[to])
        {
            vc.pb(dfs(to, v));
            vc.back().F++;
        }
    }
    sort(vc.rbegin(), vc.rend());
    int n = int(vc.size());
    int i = 0;
    if (n == 1)
    {
        return vc[0];
    }
    if (vc[0].F == vc[1].F && vc[0].F * 2 >= len)
    {
        ll izm = 0;
        ll sum = 0;
        while(i < n && vc[i].F == vc[0].F)
        {
            sum += vc[i].S;
//            cerr << vc[i].S;
            i++;
        }
        i = 0;
       while(i < n && vc[i].F == vc[0].F)
       {
            izm += vc[i].S * (sum - vc[i].S);
            i++;
       }
       if (vc[0].F * 2 > len)
       {
           len = vc[0].F * 2;
           ans = izm;
       }
       else
       {
           ans += izm;
       }
    }
    else
    if (vc[0].F != vc[1].F && vc[0].F + vc[1].F >= len)
    {
        ll izm = 0;
        i = 1;
       while(i < n && vc[i].F == vc[1].F)
       {
            izm += vc[0].S * vc[i].S;
            i++;
       }
       if (vc[0].F + vc[1].F > len)
       {
           ans = izm * 2;
       }
       else
       {
           ans += izm * 2;
       }
       len = vc[0].F + vc[1].F;
    }
    i = 0;
    ll ret = 0;
    while(i < n && vc[i].F == vc[0].F)
    {
        ret += vc[i].S;
        i++;
    }
    return {vc[0].F, ret};
}

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;
    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])
        {
            pair <int, int> pp = dfs(i, i);
            cc[i] = pp;
        }
    }
    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 / 2;
                    for(t; t > 0; t--)
                    {
                        LEN++;
                        if (LEN + cc[v].F > len)
                        {
                            len = LEN + cc[v].F;
                            ans = CNT * cc[v].S;
                        }
                        else
                        if (LEN + cc[v].F == len)
                        {
                            ans += CNT * cc[v].S;
                        }
                        for(auto ttt:g[v])
                        {
                            if (cycle[ttt] && ttt != pr)
                            {
                                pr = v;
                                v = ttt;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
//    cerr << len << endl;
    cout << (ans >> 1);
    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5128 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Correct 7 ms 5120 KB Output is correct
15 Correct 6 ms 5120 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 5376 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 9 ms 5376 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 9 ms 5248 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 8312 KB Output is correct
2 Correct 77 ms 10048 KB Output is correct
3 Execution timed out 1561 ms 14068 KB Time limit exceeded
4 Halted 0 ms 0 KB -