| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 120725 | 2019-06-25T10:36:20 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];
int done[100009];
int comp[100009];
int mp[1000009];
int crnt=0;
void dfs1(int node,int p){
child[node]=1;
done[node]=1;
comp[node]=crnt;
mp[crnt]++;
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){
done[node]=1;
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]*(mp[comp[node]]-child[u]-1);
}
else{
sum+=(mp[comp[node]]-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);
}
for(int i=0;i<n;i++){
if(done[i]==0){
dfs1(i,i);
crnt++;
}
}
memset(done,0,sizeof(done));
for(int i=0;i<n;i++){
if(done[i]==0){
dfs2(i,i);
}
}
/* 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 | 789 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 | 789 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 | 1093 ms | 224000 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3200 KB | Output is correct |
| 2 | Correct | 5 ms | 3200 KB | Output is correct |
| 3 | Correct | 5 ms | 3200 KB | Output is correct |
| 4 | Correct | 4 ms | 3200 KB | Output is correct |
| 5 | Correct | 5 ms | 3116 KB | Output is correct |
| 6 | Correct | 5 ms | 3200 KB | Output is correct |
| 7 | Correct | 5 ms | 3200 KB | Output is correct |
| 8 | Correct | 4 ms | 3200 KB | Output is correct |
| 9 | Correct | 5 ms | 3200 KB | Output is correct |
| 10 | Correct | 5 ms | 3200 KB | Output is correct |
| 11 | Correct | 5 ms | 3220 KB | Output is correct |
| 12 | Correct | 5 ms | 3200 KB | Output is correct |
| 13 | Correct | 5 ms | 3200 KB | Output is correct |
| 14 | Correct | 5 ms | 3200 KB | Output is correct |
| 15 | Correct | 12 ms | 3200 KB | Output is correct |
| 16 | Correct | 5 ms | 3072 KB | Output is correct |
| 17 | Correct | 8 ms | 3200 KB | Output is correct |
| 18 | Correct | 4 ms | 3200 KB | Output is correct |
| 19 | Correct | 5 ms | 3200 KB | Output is correct |
| 20 | Correct | 5 ms | 3200 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 134 ms | 9128 KB | Output is correct |
| 2 | Correct | 140 ms | 9300 KB | Output is correct |
| 3 | Correct | 144 ms | 9148 KB | Output is correct |
| 4 | Correct | 129 ms | 9180 KB | Output is correct |
| 5 | Correct | 128 ms | 9204 KB | Output is correct |
| 6 | Correct | 154 ms | 12156 KB | Output is correct |
| 7 | Correct | 157 ms | 11464 KB | Output is correct |
| 8 | Correct | 147 ms | 10844 KB | Output is correct |
| 9 | Correct | 140 ms | 10108 KB | Output is correct |
| 10 | Correct | 134 ms | 9124 KB | Output is correct |
| 11 | Correct | 137 ms | 10564 KB | Output is correct |
| 12 | Correct | 131 ms | 10460 KB | Output is correct |
| 13 | Correct | 119 ms | 10488 KB | Output is correct |
| 14 | Correct | 103 ms | 10104 KB | Output is correct |
| 15 | Correct | 99 ms | 9816 KB | Output is correct |
| 16 | Correct | 67 ms | 8696 KB | Output is correct |
| 17 | Correct | 95 ms | 10600 KB | Output is correct |
| 18 | Correct | 98 ms | 10696 KB | Output is correct |
| 19 | Correct | 102 ms | 10620 KB | Output is correct |
| 20 | Correct | 96 ms | 10600 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 3072 KB | Output is correct |
| 2 | Correct | 5 ms | 3200 KB | Output is correct |
| 3 | Runtime error | 898 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 | 134 ms | 9208 KB | Output is correct |
| 2 | Correct | 147 ms | 9080 KB | Output is correct |
| 3 | Execution timed out | 1148 ms | 1008692 KB | Time limit exceeded |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 789 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 | 789 ms | 1048576 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |