oj.uz

Submission #710226

# Submission time Handle Problem Language Result Execution time Memory
710226 2023-03-15T05:52:08 Z lam Duathlon (APIO18_duathlon) C++14
8 / 100
 118 ms 23624 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int n,m;
vector <int> adj[maxn];
stack <int> st;
int l[maxn],t[maxn],cnt,scc,id[maxn];
int dp[maxn],dp2[maxn],s[maxn];
vector <int> adj2[maxn];
int ans = 0LL;

void dfs(int x, int p)
{
    st.push(x);
    l[x] = t[x] = ++cnt;
    for (int i:adj[x])
        if (i!=p)
    {
        if (!t[i])
        {
            dfs(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);
    }
}

void dfs2(int x, int p)
{
    dp[x] = 0;
    for (int i:adj2[x])
        if (i!=p)
    {
        dfs2(i,x);
        dp[x] = (dp[x] + dp[i] + s[i]) ;
    }
}

void dfs3(int x, int p, int val)
{
    dp2[x] = val;
    vector <int> pre,suf;
    for (int i:adj2[x])
        if (i!=p)
    {
        pre.push_back((dp[i]+s[i]) );
        suf.push_back((dp[i]+s[i]) );
    }
    val = (val + s[x]) ;
    for (int i=1; i<pre.size(); i++) pre[i] = (pre[i-1] + pre[i]) ;
    for (int i=suf.size()-2; i>=0; i--) suf[i] = (suf[i+1] + suf[i]) ;
    int cnt=0;
    for (int i:adj2[x])
        if (i!=p)
        {
            int val2 = val;
            if (cnt>0) val2 = (val2 + pre[cnt-1]) ;
            if (cnt+1<suf.size()) val2 = (val2 + suf[cnt+1]) ;
            cnt++;
            dfs3(i,x,val2);
        }
}
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;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cnt = scc= 0;
    vector <int> root;
    for (int i=1; i<=n; i++) if (!t[i]) dfs(i,i), root.push_back(id[i]);
    for (int i=1; i<=n; i++)
        for (int j:adj[i])
            if (id[i]!=id[j])
    {
        adj2[id[i]].push_back(id[j]);
    }
    for (int i:root) dfs2(i,i);
    for (int i:root) dfs3(i,i,0);
//    assert(scc>1);
//    if (scc==1)
//    {
//        ans = n*(n-1)*(n-2);
//        cout<<ans<<'\n';
//        return 0;
//    }
    ans = 0LL;
    for (int i=1; i<=scc; i++)
    {
        int sl = s[i];
        int temp = 0;
        assert(sl==1||(sl>=3&&dp[i]==0&&dp2[i]==0));
        if (sl>=3)
        {

            temp = sl*(sl-1)*(sl-2);
            ans = (ans + temp);
        }
//        if (sl>=2)
//        {
//            temp = (sl-1)*(sl-2) + sl-1;
////            cerr<<temp<<endl;
//            ans = (ans + temp*dp[i]*2);
//            ans = (ans + temp*dp2[i]*2);
//        }
//        ans = (ans + sl*dp[i]*dp2[i]*2);
    }
//    assert(scc==1);
//    int res = 0;
    for (int i:root)
    {
        if (dp[i]==0) continue;
        int p = dp[i] + s[i];
        for (int j=1; j<=p; j++) ans += 2*(j-1)*(p-j);
    }
//    cout<<res<<'\n';
//    cout<<ans<<'\n';
    cout<<ans<<'\n';
}

Compilation message

count_triplets.cpp: In function 'void dfs3(long long int, long long int, long long int)':
count_triplets.cpp:63: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]
   63 |     for (int i=1; i<pre.size(); i++) pre[i] = (pre[i-1] + pre[i]) ;
      |                   ~^~~~~~~~~~~
count_triplets.cpp:71:22: 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]
   71 |             if (cnt+1<suf.size()) val2 = (val2 + suf[cnt+1]) ;
      |                 ~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Runtime error 10 ms 10068 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Runtime error 10 ms 10068 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17464 KB Output is correct
2 Correct 85 ms 17580 KB Output is correct
3 Correct 107 ms 23624 KB Output is correct
4 Correct 80 ms 17540 KB Output is correct
5 Correct 76 ms 18880 KB Output is correct
6 Correct 118 ms 21772 KB Output is correct
7 Correct 101 ms 18520 KB Output is correct
8 Correct 100 ms 19376 KB Output is correct
9 Correct 83 ms 16212 KB Output is correct
10 Correct 62 ms 16588 KB Output is correct
11 Correct 60 ms 13796 KB Output is correct
12 Correct 80 ms 13600 KB Output is correct
13 Correct 75 ms 14020 KB Output is correct
14 Correct 60 ms 13820 KB Output is correct
15 Correct 74 ms 14060 KB Output is correct
16 Correct 41 ms 13824 KB Output is correct
17 Correct 8 ms 10576 KB Output is correct
18 Correct 11 ms 10564 KB Output is correct
19 Correct 9 ms 10572 KB Output is correct
20 Correct 12 ms 10572 KB Output is correct
21 Correct 9 ms 10572 KB Output is correct
22 Correct 10 ms 10596 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Runtime error 10 ms 10068 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Runtime error 10 ms 10068 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -