oj.uz

Submission #710303

# Submission time Handle Problem Language Result Execution time Memory
710303 2023-03-15T06:53:34 Z vjudge1 Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int n,m;
vector <int> adj[maxn];
int dp[maxn],dp2[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]+1;
    }
}

void dfs2(int x, int p, int val)
{
    dp2[x] = val;
    val++;
    vector <int> pre,suf;
    for (int i:adj[x])
        if (i!=p)
    {
        pre.push_back(dp[i]+1);
        suf.push_back(dp[i]+1);
    }
    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 - 1 - val);
//    cout<<x<<" :: "<<val<<' '<<temp<<endl;
    if (temp>0&&val>0)
    ans += val*temp;
    for (int i:adj[x])
        if (i!=p)
    {
        dfs3(i,x,sz);
        val = dp[i]+1;
        temp = sz - 1 - val;
//        cout<<i<<" "<<x<<" :: "<<val<<" :: "<<temp<<endl;
        if (temp>0&&val>0) ans+=val*temp;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
//    freopen("dualthon.inp","r",stdin);
//    freopen("dualthon.out","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);
    }
    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:root) dfs3(i,i,dp[i]+1);
    cout<<ans<<'\n';
}

Compilation message

count_triplets.cpp: In function 'void dfs2(long long int, long long int, long long int)':
count_triplets.cpp:34: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]
   34 |     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 Runtime error 456 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 456 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 467284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8048 KB Output is correct
2 Correct 78 ms 8020 KB Output is correct
3 Correct 58 ms 8012 KB Output is correct
4 Correct 59 ms 8064 KB Output is correct
5 Correct 65 ms 8024 KB Output is correct
6 Correct 110 ms 20248 KB Output is correct
7 Correct 83 ms 16256 KB Output is correct
8 Correct 82 ms 14344 KB Output is correct
9 Correct 95 ms 12212 KB Output is correct
10 Correct 56 ms 8012 KB Output is correct
11 Correct 81 ms 8196 KB Output is correct
12 Correct 98 ms 8016 KB Output is correct
13 Correct 67 ms 7976 KB Output is correct
14 Correct 53 ms 8012 KB Output is correct
15 Correct 52 ms 7848 KB Output is correct
16 Correct 30 ms 7152 KB Output is correct
17 Correct 31 ms 9948 KB Output is correct
18 Correct 34 ms 10400 KB Output is correct
19 Correct 41 ms 10804 KB Output is correct
20 Correct 37 ms 9828 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Runtime error 559 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8136 KB Output is correct
2 Correct 76 ms 7928 KB Output is correct
3 Runtime error 683 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 456 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 456 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -