oj.uz

Submission #737041

# Submission time Handle Problem Language Result Execution time Memory
737041 2023-05-06T13:47:28 Z onlk97 Duathlon (APIO18_duathlon) C++14
0 / 100
 170 ms 32984 KB 
#include <bits/stdc++.h>
using namespace std;
long long n,m;
vector <int> g[100010],bc[200010];
bool visited[200010];
long long dfn[100010],lo[100010],w[200020],sz[200020],occ[200020];
stack <int> st;
int tme,curid;
void dfs(int cur){
    tme++;
    dfn[cur]=lo[cur]=tme;
    visited[cur]=1;
    st.push(cur);
    for (int i:g[cur]){
        if (!visited[i]){
            dfs(i);
            lo[cur]=min(lo[cur],lo[i]);
            if (lo[i]==dfn[cur]){
                curid++;
                bool ok=1;
                while (ok){
                    bc[st.top()].push_back(curid);
                    bc[curid].push_back(st.top());
                    w[curid]++;
                    if (st.top()==i) ok=0;
                    st.pop();
                }
                bc[cur].push_back(curid);
                bc[curid].push_back(cur);
                w[curid]++;
            }
        } else lo[cur]=min(lo[cur],dfn[i]);
    }
}
void dfs2(int cur,int prv){
    visited[cur]=1;
    sz[cur]=(cur<=n);
    long long rem=n-(cur<=n);
    occ[cur]=n*(n-1)/2;
    for (int i:bc[cur]){
        if (i==prv) continue;
        dfs2(i,cur);
        sz[cur]+=sz[i];
        occ[cur]-=sz[i]*(sz[i]-1)/2;
        rem-=sz[i];
    }
    occ[cur]-=rem*(rem-1)/2;
}
signed main(){
    cin>>n>>m;
    for (int i=0; i<m; i++){
        int u,v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    curid=n;
    for (int i=1; i<=n; i++){
        if (!visited[i]) dfs(i);
    }
    for (int i=1; i<=curid; i++) visited[i]=0;
    for (int i=1; i<=n; i++) w[i]=-1;
    for (int i=1; i<=curid; i++){
        if (!visited[i]) dfs2(i,0);
    }
    long long ans=0;
    for (int i=1; i<=curid; i++) ans+=w[i]*occ[i];
    cout<<ans*2<<'\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 25804 KB Output is correct
2 Correct 129 ms 27076 KB Output is correct
3 Incorrect 113 ms 28340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7636 KB Output is correct
5 Correct 6 ms 7508 KB Output is correct
6 Correct 6 ms 7508 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 5 ms 7508 KB Output is correct
10 Incorrect 5 ms 7508 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 23332 KB Output is correct
2 Correct 123 ms 24636 KB Output is correct
3 Correct 126 ms 24640 KB Output is correct
4 Correct 137 ms 24652 KB Output is correct
5 Correct 130 ms 24648 KB Output is correct
6 Correct 170 ms 32984 KB Output is correct
7 Correct 150 ms 30056 KB Output is correct
8 Correct 146 ms 28696 KB Output is correct
9 Correct 156 ms 27260 KB Output is correct
10 Incorrect 139 ms 24656 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 5 ms 7528 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7508 KB Output is correct
12 Correct 5 ms 7508 KB Output is correct
13 Correct 4 ms 7508 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Incorrect 5 ms 7508 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 23364 KB Output is correct
2 Correct 129 ms 24528 KB Output is correct
3 Correct 138 ms 23824 KB Output is correct
4 Correct 138 ms 22544 KB Output is correct
5 Correct 130 ms 21232 KB Output is correct
6 Correct 129 ms 20828 KB Output is correct
7 Correct 140 ms 20392 KB Output is correct
8 Correct 115 ms 20008 KB Output is correct
9 Correct 122 ms 19868 KB Output is correct
10 Correct 115 ms 19948 KB Output is correct
11 Correct 112 ms 19660 KB Output is correct
12 Correct 109 ms 19664 KB Output is correct
13 Correct 116 ms 19700 KB Output is correct
14 Correct 114 ms 21392 KB Output is correct
15 Correct 146 ms 29648 KB Output is correct
16 Correct 165 ms 27584 KB Output is correct
17 Correct 155 ms 28044 KB Output is correct
18 Correct 155 ms 26324 KB Output is correct
19 Incorrect 144 ms 22612 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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