oj.uz

Submission #710307

# Submission time Handle Problem Language Result Execution time Memory
710307 2023-03-15T06:58:43 Z lam Duathlon (APIO18_duathlon) C++14
31 / 100
 153 ms 29556 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;
bool dau[maxn];
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);
//        cout<<temp<<" : "<<dp[i]+s[i]<<' '<<s[x]<<endl;
        dp[x] = (dp[x] + dp[i] + s[i]) ;
    }
}

void dfs3(int x, int p, int val)
{
    dp2[x] = val;
//    cout<<val<<" : "<<temp<<" : "<<s[x]<<endl;
    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]) ;
//    cout<<x<<" :: "<<val<<endl;
//    for (int i:pre) cout<<i<<' '; cout<<"@@@@@@@@@@@"<<endl;
//    for (int i:suf) cout<<i<<' '; cout<<"@@@@@@@@@@@"<<endl;
    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]) ;
//    cout<<(int)suf.size()<<"@%$@%#$@"<<endl;
    int cnt2=0;
    for (int i:adj2[x])
        if (i!=p)
        {
            int val2 = val;
//            cerr<<val2<<' '<<cnt2<<" -> ";
            if (cnt2>0) val2 = (val2 + pre[cnt2-1]) ;
            if (cnt2<=(int)suf.size()-2) val2 = (val2 + suf[cnt2+1]) ;
//             cerr<<val<<endl;
            cnt2++;
            dfs3(i,x,val2);
        }
}
void dfs4(int x, int p, int sz)
{
    int val = dp2[x];
    int temp = (sz - s[x] - val);
    if (temp>0&&val>0)
    ans += s[x]*val*temp;
    for (int i:adj2[x])
        if (i!=p)
    {
        dfs4(i,x,sz);
        val = dp[i]+s[i];
        temp = sz - s[x] - val;
        if (temp>0&&val>0) ans+=s[x]*val*temp;
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
//    freopen("dualthon.inp","r",stdin);
//    freopen("dualthon.ans","w",stdout);
    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=1; i<=scc; i++)
    {
        sort(adj2[i].begin(),adj2[i].end());
        adj2[i].resize(unique(adj2[i].begin(),adj2[i].end())-adj2[i].begin());
    }
    for (int i:root) dfs2(i,i);
    for (int i:root) dfs3(i,i,0);
    for (int i=1; i<=scc; i++)
    {
        int sl = s[i];
//        cout<<i<<" := "<<dp[i]<<' '<<dp2[i]<<endl;
        int temp = 0;
        if (sl>=3)
        {
            temp = sl*(sl-1)*(sl-2);
            ans = (ans + temp);
        }
        if (sl>=2)
        {
            temp = (sl-1)*(sl-1);
//            cout<<temp<<" "<<dp[i]<<' '<<dp2[i]<<endl;
            ans += temp*dp[i]*2;
            ans += temp*dp2[i]*2;
        }
    }
    for (int i:root) dfs4(i,i,dp[i]+s[i]);
    cout<<ans<<'\n';
}

Compilation message

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

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 3 ms 4948 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 5 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 3 ms 4948 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 5 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 83 ms 17560 KB Output is correct
2 Correct 89 ms 17620 KB Output is correct
3 Correct 101 ms 23700 KB Output is correct
4 Correct 70 ms 17612 KB Output is correct
5 Correct 80 ms 19016 KB Output is correct
6 Correct 92 ms 21884 KB Output is correct
7 Correct 109 ms 18664 KB Output is correct
8 Correct 77 ms 19508 KB Output is correct
9 Correct 85 ms 16420 KB Output is correct
10 Correct 75 ms 16816 KB Output is correct
11 Correct 75 ms 13864 KB Output is correct
12 Correct 56 ms 13768 KB Output is correct
13 Correct 55 ms 14148 KB Output is correct
14 Correct 56 ms 13976 KB Output is correct
15 Correct 45 ms 14192 KB Output is correct
16 Correct 55 ms 13872 KB Output is correct
17 Correct 12 ms 10536 KB Output is correct
18 Correct 12 ms 10664 KB Output is correct
19 Correct 10 ms 10664 KB Output is correct
20 Correct 9 ms 10572 KB Output is correct
21 Correct 9 ms 10536 KB Output is correct
22 Correct 8 ms 10584 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5124 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 3 ms 5264 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 5 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5180 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 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 3 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 125 ms 17100 KB Output is correct
2 Correct 139 ms 17100 KB Output is correct
3 Correct 90 ms 17156 KB Output is correct
4 Correct 98 ms 17204 KB Output is correct
5 Correct 96 ms 17176 KB Output is correct
6 Correct 139 ms 29556 KB Output is correct
7 Correct 125 ms 25868 KB Output is correct
8 Correct 117 ms 23572 KB Output is correct
9 Correct 124 ms 21392 KB Output is correct
10 Correct 153 ms 17116 KB Output is correct
11 Correct 87 ms 17168 KB Output is correct
12 Correct 80 ms 17200 KB Output is correct
13 Correct 86 ms 17152 KB Output is correct
14 Correct 73 ms 16808 KB Output is correct
15 Correct 102 ms 16372 KB Output is correct
16 Correct 58 ms 14876 KB Output is correct
17 Correct 63 ms 19220 KB Output is correct
18 Correct 53 ms 19680 KB Output is correct
19 Correct 60 ms 20144 KB Output is correct
20 Correct 57 ms 19044 KB Output is correct

Subtask #6
0 / 15.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 Incorrect 4 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 98 ms 17192 KB Output is correct
2 Correct 89 ms 16920 KB Output is correct
3 Incorrect 93 ms 15212 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 3 ms 4948 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 5 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 3 ms 4948 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 5 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -