oj.uz

Submission #710353

# Submission time Handle Problem Language Result Execution time Memory
710353 2023-03-15T07:35:56 Z lam Duathlon (APIO18_duathlon) C++14
31 / 100
 157 ms 41112 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int n,m;
vector <int> adj[maxn],adj2[maxn];
int dp[maxn],dp2[maxn];
stack <int> st;
int l[maxn],t[maxn],cnt2;
int scc, id[maxn], s[maxn];
bool dau[maxn];
vector <int> root;
int ans = 0LL;
void dfs(int x, int p)
{
    dau[x] = 1;
    dp[x] = 0;
    for (int i:adj[x])
        if (i!=p)
    {
        dfs(i,x);
        dp[x] += dp[i]+s[i];
    }
}

void dfs2(int x, int p, int val)
{
    dp2[x] = val;
    val+=s[x];
    vector <int> pre,suf;
    for (int i:adj[x])
        if (i!=p)
    {
        pre.push_back(dp[i]+s[i]);
        suf.push_back(dp[i]+s[i]);
    }
    for (int i=1; i<pre.size(); i++) pre[i]+=pre[i-1];
    for (int i=suf.size()-2; i>=0; i--) suf[i]+=suf[i+1];
    int cnt=0;
    for (int i:adj[x])
        if (i!=p)
    {
        int val2 = val;
        if (cnt>0) val2 += pre[cnt-1];
        if (cnt<(int)suf.size()-1) val2+=suf[cnt+1];
        cnt++;
        dfs2(i,x,val2);
    }
}

void dfs3(int x, int p, int sz)
{
    int val = dp2[x];
    int temp = (sz - s[x] - val);
    if (temp>0&&val>0)
    ans += val*temp*s[x];
    if (val>0&&s[x]>1) ans += (s[x]-1)*(s[x]-1)*val*2;
    for (int i:adj[x])
        if (i!=p)
    {
        dfs3(i,x,sz);
        val = dp[i]+s[i];
        temp = sz - s[x] - val;
        if (temp>0&&val>0) ans+=val*temp*s[x];
        if (val>0&&s[x]>1) ans+=(s[x]-1)*(s[x]-1)*val*2;
    }
}

void build(int x, int p)
{
    st.push(x);
    l[x]=t[x]=++cnt2;
    for (int i:adj2[x])
        if (i!=p)
    {
        if (t[i]==0)
        {
            build(i,x);
            l[x]=min(l[x],l[i]);
        }
        else l[x]=min(l[x],t[i]);
    }
    if (l[x]==t[x])
    {
        scc++; int temp;
        do
        {
            temp = st.top(); st.pop();
            s[scc] ++ ;
            id[temp] = scc;
        }
        while (temp!=x);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        int u,v; cin>>u>>v;
        adj2[u].push_back(v);
        adj2[v].push_back(u);
    }
    scc=cnt2=0;
    for (int i=1; i<=n; i++) if (!t[i]) build(i,i);
    for (int i=1; i<=n; i++)
        for (int j:adj2[i])
            if (id[i]!=id[j])
                adj[id[i]].push_back(id[j]);
    n = scc;
    fill_n(dau,n+1,0);
    for (int i=1; i<=n; i++) if (!dau[i]) dfs(i,i), root.push_back(i);
    for (int i:root) dfs2(i,i,0);
    for (int i=1; i<=n; i++) if (s[i]>=3) ans += s[i]*(s[i]-1)*(s[i]-2);
    for (int i:root) dfs3(i,i,dp[i]+s[i]);
    cout<<ans<<'\n';
}

Compilation message

count_triplets.cpp: In function 'void dfs2(long long int, long long int, long long int)':
count_triplets.cpp:37:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=1; i<pre.size(); i++) pre[i]+=pre[i-1];
      |                   ~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 17500 KB Output is correct
2 Correct 50 ms 17576 KB Output is correct
3 Correct 100 ms 25768 KB Output is correct
4 Correct 61 ms 18108 KB Output is correct
5 Correct 74 ms 20684 KB Output is correct
6 Correct 100 ms 27452 KB Output is correct
7 Correct 106 ms 18872 KB Output is correct
8 Correct 138 ms 22860 KB Output is correct
9 Correct 108 ms 16444 KB Output is correct
10 Correct 67 ms 17564 KB Output is correct
11 Correct 63 ms 13900 KB Output is correct
12 Correct 80 ms 13868 KB Output is correct
13 Correct 54 ms 14272 KB Output is correct
14 Correct 57 ms 13916 KB Output is correct
15 Correct 43 ms 14276 KB Output is correct
16 Correct 52 ms 14020 KB Output is correct
17 Correct 9 ms 10668 KB Output is correct
18 Correct 13 ms 10704 KB Output is correct
19 Correct 9 ms 10700 KB Output is correct
20 Correct 9 ms 10700 KB Output is correct
21 Correct 9 ms 10704 KB Output is correct
22 Correct 10 ms 10748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 ms 5076 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 5 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 5 ms 5204 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 3 ms 5204 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 17248 KB Output is correct
2 Correct 155 ms 17248 KB Output is correct
3 Correct 126 ms 17200 KB Output is correct
4 Correct 95 ms 17304 KB Output is correct
5 Correct 87 ms 17304 KB Output is correct
6 Correct 156 ms 41112 KB Output is correct
7 Correct 157 ms 25908 KB Output is correct
8 Correct 112 ms 23756 KB Output is correct
9 Correct 106 ms 21540 KB Output is correct
10 Correct 112 ms 17196 KB Output is correct
11 Correct 90 ms 17240 KB Output is correct
12 Correct 110 ms 17288 KB Output is correct
13 Correct 98 ms 17188 KB Output is correct
14 Correct 102 ms 17024 KB Output is correct
15 Correct 81 ms 16664 KB Output is correct
16 Correct 51 ms 15064 KB Output is correct
17 Correct 66 ms 19268 KB Output is correct
18 Correct 82 ms 19772 KB Output is correct
19 Correct 58 ms 20136 KB Output is correct
20 Correct 68 ms 19180 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 17260 KB Output is correct
2 Correct 113 ms 17012 KB Output is correct
3 Incorrect 81 ms 15204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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