oj.uz

답안 #925337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925337 2024-02-11T13:06:25 Z codefox 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 111 ms 29180 KB 
#include<bits/stdc++.h>
    
using namespace std;
    
#define int ll    
#define ll long long
#define pii pair<int, int>
    
vector<vector<int>> graph;
vector<vector<int>> cgraph;
vector<vector<ll>> opt;
vector<int> comp;
vector<int> low;
vector<int> num;
vector<int> vis;
vector<int> art;
vector<ll> compsize;
stack<int> s;
ll sol = 0;
int c = 0;
int d = 0;
ll n, m;
    
void dfs(int i, int p)
{
    num[i] = low[i] = ++c;
    s.push(i);
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        if (!num[ele]) 
        {
            dfs(ele, i);
            if (low[ele]==num[i])
            {
                while(s.top() != ele)
                {
                    comp[s.top()] = d;
                    compsize[d]++;
                    s.pop();
                }
                comp[s.top()] = d;
                compsize[d]++;
                s.pop();
                d++;
            }
        }
        low[i] = min(low[i], low[ele]);
    }
    if (num[i]==low[i])
    {
        art[d] = 1;
        while (s.top() != i)
        {
            comp[s.top()] = d;
            compsize[d]++;
            s.pop();
        }
        comp[i] = d;
        compsize[d]++;
        s.pop();
        d++;
    }
}
    
void dfs2(int i)
{
    vis[i] = 1;
    opt[i][0] = compsize[i];
    opt[i][1] = compsize[i]*(compsize[i]-1);
    sol += (compsize[i]-2)*compsize[i]*(compsize[i]-1);
    if (!art[i]) sol += compsize[i]*(compsize[i]-1);
    vector<array<ll, 2>> ones;
    ll sum = 0;
    for (int ele:cgraph[i])
    {
        if (vis[ele]) continue;
        dfs2(ele);
        opt[i][0] += opt[ele][0];
        opt[i][1] += opt[ele][1] + opt[ele][0]*compsize[i];
        sum += opt[ele][0];
        ones.push_back({opt[ele][0], opt[ele][1]});
        sol += opt[ele][0]*(compsize[i]-1)*(compsize[i]-2)*2;
        sol += opt[ele][0]*(compsize[i]-1)*2;
        if (!art[i]) sol += opt[ele][0]*(compsize[i]-1)*2;
        sol += opt[ele][1]*compsize[i]*2;
    }

    for (array<ll, 2> ele:ones)
    {
        if (!art[i]) sol += ele[0]*(sum-ele[0])*(compsize[i]+1);
        else         sol += ele[0]*(sum-ele[0])*(compsize[i]);
        sol += ele[1]*(sum-ele[0])*2;
    }
}
    
int32_t main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    cin >> n >> m;
    graph.assign(n, vector<int>());
    cgraph.assign(n, vector<int>());
    compsize.assign(n, 0);
    low.assign(n, 0);
    num.assign(n, 0);
    comp.assign(n, -1);
    vis.assign(n, 0);
    art.assign(n, 0);
    opt.assign(n, vector<ll>(2, 0));
    
    for (int i =0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    for (int i = 0; i < n; i++)
    {
        if (!num[i]) 
        {
            dfs(i, -1);
        }
    }
    
    for (int i = 0; i <n; i++)
    {
        for (int ele:graph[i])
        {
            if (comp[i] == comp[ele]) continue;
            cgraph[comp[i]].push_back(comp[ele]);
        }
    }
    
    for (int i = 0; i < n; i++)
    {
        if (!vis[comp[i]])
        {
            dfs2(comp[i]);
        }
    }

    cout << sol << "\n";
    
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 344 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 344 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 26928 KB Output is correct
2 Correct 76 ms 26868 KB Output is correct
3 Correct 82 ms 25676 KB Output is correct
4 Correct 77 ms 24916 KB Output is correct
5 Correct 76 ms 22988 KB Output is correct
6 Correct 80 ms 24824 KB Output is correct
7 Correct 82 ms 22996 KB Output is correct
8 Correct 85 ms 23376 KB Output is correct
9 Correct 90 ms 21584 KB Output is correct
10 Correct 93 ms 22080 KB Output is correct
11 Correct 72 ms 20564 KB Output is correct
12 Correct 69 ms 20304 KB Output is correct
13 Correct 77 ms 20552 KB Output is correct
14 Correct 68 ms 20304 KB Output is correct
15 Correct 63 ms 20116 KB Output is correct
16 Correct 58 ms 19792 KB Output is correct
17 Correct 11 ms 15196 KB Output is correct
18 Correct 11 ms 15348 KB Output is correct
19 Correct 11 ms 15192 KB Output is correct
20 Correct 11 ms 15196 KB Output is correct
21 Correct 11 ms 15196 KB Output is correct
22 Correct 11 ms 15196 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 616 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 22612 KB Output is correct
2 Correct 88 ms 22612 KB Output is correct
3 Correct 96 ms 22612 KB Output is correct
4 Correct 96 ms 22612 KB Output is correct
5 Correct 85 ms 22636 KB Output is correct
6 Correct 97 ms 29180 KB Output is correct
7 Correct 102 ms 27476 KB Output is correct
8 Correct 98 ms 26424 KB Output is correct
9 Correct 95 ms 25168 KB Output is correct
10 Correct 89 ms 22704 KB Output is correct
11 Correct 89 ms 22756 KB Output is correct
12 Correct 87 ms 22688 KB Output is correct
13 Correct 89 ms 22672 KB Output is correct
14 Correct 81 ms 22356 KB Output is correct
15 Correct 74 ms 21712 KB Output is correct
16 Correct 52 ms 20128 KB Output is correct
17 Correct 76 ms 25284 KB Output is correct
18 Correct 76 ms 25184 KB Output is correct
19 Correct 78 ms 25016 KB Output is correct
20 Correct 75 ms 24540 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 23004 KB Output is correct
2 Correct 89 ms 22356 KB Output is correct
3 Incorrect 111 ms 22356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 344 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 344 KB Output isn't correct
23 Halted 0 ms 0 KB -