| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 72118 | 2018-08-26T05:22:36 Z | KLPP | Duathlon (APIO18_duathlon) | C++14 | 235 ms | 58792 KB |
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long int lld;
lld DP[1000000];
bool visited[1000000];
vector<int>nei[1000000];
lld ans;
bool visited2[1000000];
void DFS(int node,lld dist){//cout<<node+1<<" "<<dist<<endl;
visited[node]=true;
lld sum=0;
//lld square=0;
//lld totaldist=0;
for(int i=0;i<nei[node].size();i++){
int v=nei[node][i];
if(!visited[v]){
DFS(v,dist+1);
sum+=DP[v];
//square+=DP[v]*DP[v];
}
}
DP[node]=sum+1;
//ans+=sum*sum-square;
//cout<<sum*sum-square<<" "<<node+1<<endl;
//ans+=dist*(dist-1);
}
void DFS2(int node,lld componentsize){
visited2[node]=true;
lld sq=componentsize-DP[node];
sq*=sq;
for(int i=0;i<nei[node].size();i++){
int v=nei[node][i];
if(!visited2[v]){
DFS2(v,componentsize);
sq+=DP[v]*DP[v];
}
}
ans+=(componentsize-1)*(componentsize-1)-sq;
//cout<<(componentsize-1)*(componentsize-1)-sq<<" "<<node+1<<endl;
}
int main(){
int n,m;
cin>>n>>m;
int edges[n][2];
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
x--;y--;
edges[i][0]=x;
edges[i][1]=y;
nei[x].push_back(y);
nei[y].push_back(x);
}
if(n>50){
ans=0;
for(int i=0;i<n;i++){
DP[i]=-1;
visited[i]=false;
visited2[i]=false;
}
for(int i=0;i<n;i++){
if(!visited[i]){
DFS(i,0);
DFS2(i,DP[i]);
}
}//for(int i=0;i<n;i++)cout<<DP[i]<<" "<<i+1<<endl;
cout<<ans<<endl;
return 0;
}
int component[n][n];
for(int node=0;node<n;node++){
vector<int>graph[n];
for(int j=0;j<m;j++){
if(edges[j][0]!=node && edges[j][1]!=node){
graph[edges[j][0]].push_back(edges[j][1]);
graph[edges[j][1]].push_back(edges[j][0]);
}
}
int color=0;
for(int i=0;i<n;i++)component[node][i]=-1;
for(int i=0;i<n;i++){
if(component[node][i]==-1){
component[node][i]=color;
queue<int>q;
q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
//cout<<u<<" ";
for(int j=0;j<graph[u].size();j++){
int v=graph[u][j];
if(component[node][v]==-1){
component[node][v]=color;
q.push(v);
}
}
}
color++;//cout<<endl;
}
}
/*for(int i=0;i<n;i++)cout<<component[node][i]<<" ";
cout<<endl;*/
}
int cnt=0;
for(int s=0;s<n;s++){
for(int f=0;f<n;f++){
for(int c=0;c<n;c++){
if(s!=c && s!=f && f!=c){
bool b=true;
for(int i=0;i<n;i++){
if(i!=c){
if(component[i][c]!=component[i][s] && component[i][c]!=component[i][f]){
b=false;
}}
}cnt+=b;
/*if(b){
cout<<s<<" "<<f<<" "<<c<<endl;
}*/
}
}
}
}
cout<<cnt<<endl;
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 23800 KB | Output is correct |
| 2 | Runtime error | 46 ms | 47588 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 23800 KB | Output is correct |
| 2 | Runtime error | 46 ms | 47588 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 208 ms | 58792 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 23 ms | 58792 KB | Output is correct |
| 2 | Correct | 25 ms | 58792 KB | Output is correct |
| 3 | Correct | 24 ms | 58792 KB | Output is correct |
| 4 | Correct | 26 ms | 58792 KB | Output is correct |
| 5 | Correct | 25 ms | 58792 KB | Output is correct |
| 6 | Correct | 27 ms | 58792 KB | Output is correct |
| 7 | Correct | 23 ms | 58792 KB | Output is correct |
| 8 | Correct | 23 ms | 58792 KB | Output is correct |
| 9 | Correct | 25 ms | 58792 KB | Output is correct |
| 10 | Correct | 27 ms | 58792 KB | Output is correct |
| 11 | Correct | 25 ms | 58792 KB | Output is correct |
| 12 | Correct | 26 ms | 58792 KB | Output is correct |
| 13 | Correct | 26 ms | 58792 KB | Output is correct |
| 14 | Correct | 24 ms | 58792 KB | Output is correct |
| 15 | Correct | 22 ms | 58792 KB | Output is correct |
| 16 | Correct | 22 ms | 58792 KB | Output is correct |
| 17 | Correct | 23 ms | 58792 KB | Output is correct |
| 18 | Correct | 22 ms | 58792 KB | Output is correct |
| 19 | Correct | 23 ms | 58792 KB | Output is correct |
| 20 | Correct | 23 ms | 58792 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 161 ms | 58792 KB | Output is correct |
| 2 | Correct | 208 ms | 58792 KB | Output is correct |
| 3 | Correct | 182 ms | 58792 KB | Output is correct |
| 4 | Correct | 185 ms | 58792 KB | Output is correct |
| 5 | Correct | 200 ms | 58792 KB | Output is correct |
| 6 | Correct | 214 ms | 58792 KB | Output is correct |
| 7 | Correct | 235 ms | 58792 KB | Output is correct |
| 8 | Correct | 209 ms | 58792 KB | Output is correct |
| 9 | Correct | 185 ms | 58792 KB | Output is correct |
| 10 | Correct | 171 ms | 58792 KB | Output is correct |
| 11 | Correct | 203 ms | 58792 KB | Output is correct |
| 12 | Correct | 188 ms | 58792 KB | Output is correct |
| 13 | Correct | 234 ms | 58792 KB | Output is correct |
| 14 | Correct | 182 ms | 58792 KB | Output is correct |
| 15 | Correct | 184 ms | 58792 KB | Output is correct |
| 16 | Correct | 125 ms | 58792 KB | Output is correct |
| 17 | Correct | 141 ms | 58792 KB | Output is correct |
| 18 | Correct | 176 ms | 58792 KB | Output is correct |
| 19 | Correct | 172 ms | 58792 KB | Output is correct |
| 20 | Correct | 150 ms | 58792 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 23 ms | 58792 KB | Output is correct |
| 2 | Correct | 24 ms | 58792 KB | Output is correct |
| 3 | Incorrect | 23 ms | 58792 KB | Output isn't correct |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 202 ms | 58792 KB | Output is correct |
| 2 | Correct | 217 ms | 58792 KB | Output is correct |
| 3 | Incorrect | 209 ms | 58792 KB | Output isn't correct |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 23800 KB | Output is correct |
| 2 | Runtime error | 46 ms | 47588 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 23800 KB | Output is correct |
| 2 | Runtime error | 46 ms | 47588 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |