# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
120707 | 2019-06-25T09:44:18 Z | _demon_ | Duathlon (APIO18_duathlon) | C++14 | 1000 ms | 1048576 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,m; ll child[100009]; ll ans; ll w[100009]; vector<ll>v[100009]; void dfs1(int node,int p){ child[node]=1; if(node!=p)w[node]=w[p]+1; for(int i=0;i<v[node].size();i++){ int u=v[node][i]; if(u==p)continue; dfs1(u,node); child[node]+=child[u]; } } int a[100009]; void dfs2(int node,int p){ ll sum=0; for(int i=0;i<v[node].size();i++){ int u=v[node][i]; if(w[u]>w[node]){ sum+=child[u]*(n-child[u]-1); } else{ sum+=(n-child[node])*(child[node]-1); } } a[node]=sum; ans+=sum; for(int i=0;i<v[node].size();i++){ int u=v[node][i]; if(u==p)continue; dfs2(u,node); } } int main(){ cin>>n>>m; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; a--;b--; v[a].push_back(b); v[b].push_back(a); } dfs1(0,0); // for(int i=0;i<n;i++)cout<<w[i]<<" "; // cout<<endl; dfs2(0,0); // for(int i=0;i<n;i++)cout<<a[i]<<" "; // cout<<endl; cout<<ans<<endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 808 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 808 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1103 ms | 238544 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2816 KB | Output is correct |
2 | Correct | 0 ms | 2688 KB | Output is correct |
3 | Correct | 6 ms | 2816 KB | Output is correct |
4 | Correct | 5 ms | 2816 KB | Output is correct |
5 | Correct | 5 ms | 2816 KB | Output is correct |
6 | Correct | 6 ms | 2816 KB | Output is correct |
7 | Correct | 5 ms | 2816 KB | Output is correct |
8 | Correct | 4 ms | 2688 KB | Output is correct |
9 | Correct | 5 ms | 2816 KB | Output is correct |
10 | Incorrect | 4 ms | 2688 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 109 ms | 8312 KB | Output is correct |
2 | Correct | 123 ms | 9680 KB | Output is correct |
3 | Correct | 124 ms | 9592 KB | Output is correct |
4 | Correct | 113 ms | 9764 KB | Output is correct |
5 | Correct | 134 ms | 9564 KB | Output is correct |
6 | Correct | 183 ms | 12556 KB | Output is correct |
7 | Correct | 149 ms | 11768 KB | Output is correct |
8 | Correct | 149 ms | 11356 KB | Output is correct |
9 | Correct | 131 ms | 10652 KB | Output is correct |
10 | Incorrect | 118 ms | 9592 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2688 KB | Output is correct |
2 | Correct | 5 ms | 2688 KB | Output is correct |
3 | Runtime error | 875 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 140 ms | 8416 KB | Output is correct |
2 | Correct | 232 ms | 9564 KB | Output is correct |
3 | Execution timed out | 1146 ms | 1032756 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 808 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 808 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |