# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
49356 |
2018-05-27T12:24:05 Z |
노영훈(#1273, Diuven) |
Duathlon (APIO18_duathlon) |
C++ |
|
1000 ms |
1048576 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;
vector<int> G[MX];
int n;
ll ans;
bool valid(int s, int m, int e){
return false;
}
void solve1(){
for(int s=1; s<=n; s++)
for(int m=1; m<=n; m++)
for(int e=s+1; e<=n; e++)
if(s==m || m==e)
ans+=2*valid(s,m,e);
}
int sz[MX];
int dfs2(int v){
sz[v]=1;
for(int x:G[v]){
if(sz[x]!=0) continue;
sz[v]+=dfs2(x);
}
return sz[v];
}
void dfs3(int v, int n, int p){
ll sum=1LL*(n-1)*(n-1)-1LL*(n-sz[v])*(n-sz[v]);
for(int x:G[v]){
if(x==p) continue;
sum-=1LL*sz[x]*sz[x];
dfs3(x,n,v);
}
ans+=sum;
}
void solve2(){
for(int i=1; i<=n; i++)
if(sz[i]==0){
dfs3(i, dfs2(i), 0);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int m;
cin>>n>>m;
for(int i=1, u, v; i<=m; i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
solve2();
/*
if(false && n<=50){
solve1();
}
else{
solve2();
}
*/
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1118 ms |
1048576 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1118 ms |
1048576 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1084 ms |
1048576 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1048576 KB |
Output is correct |
2 |
Correct |
4 ms |
1048576 KB |
Output is correct |
3 |
Correct |
4 ms |
1048576 KB |
Output is correct |
4 |
Correct |
4 ms |
1048576 KB |
Output is correct |
5 |
Correct |
4 ms |
1048576 KB |
Output is correct |
6 |
Correct |
4 ms |
1048576 KB |
Output is correct |
7 |
Correct |
4 ms |
1048576 KB |
Output is correct |
8 |
Correct |
4 ms |
1048576 KB |
Output is correct |
9 |
Correct |
5 ms |
1048576 KB |
Output is correct |
10 |
Correct |
4 ms |
1048576 KB |
Output is correct |
11 |
Correct |
4 ms |
1048576 KB |
Output is correct |
12 |
Correct |
4 ms |
1048576 KB |
Output is correct |
13 |
Correct |
5 ms |
1048576 KB |
Output is correct |
14 |
Correct |
4 ms |
1048576 KB |
Output is correct |
15 |
Correct |
5 ms |
1048576 KB |
Output is correct |
16 |
Correct |
5 ms |
1048576 KB |
Output is correct |
17 |
Correct |
4 ms |
1048576 KB |
Output is correct |
18 |
Correct |
4 ms |
1048576 KB |
Output is correct |
19 |
Correct |
4 ms |
1048576 KB |
Output is correct |
20 |
Correct |
4 ms |
1048576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
1048576 KB |
Output is correct |
2 |
Correct |
84 ms |
1048576 KB |
Output is correct |
3 |
Correct |
51 ms |
1048576 KB |
Output is correct |
4 |
Correct |
70 ms |
1048576 KB |
Output is correct |
5 |
Correct |
57 ms |
1048576 KB |
Output is correct |
6 |
Correct |
128 ms |
1048576 KB |
Output is correct |
7 |
Correct |
118 ms |
1048576 KB |
Output is correct |
8 |
Correct |
129 ms |
1048576 KB |
Output is correct |
9 |
Correct |
158 ms |
1048576 KB |
Output is correct |
10 |
Correct |
121 ms |
1048576 KB |
Output is correct |
11 |
Correct |
91 ms |
1048576 KB |
Output is correct |
12 |
Correct |
88 ms |
1048576 KB |
Output is correct |
13 |
Correct |
84 ms |
1048576 KB |
Output is correct |
14 |
Correct |
88 ms |
1048576 KB |
Output is correct |
15 |
Correct |
73 ms |
1048576 KB |
Output is correct |
16 |
Correct |
42 ms |
1048576 KB |
Output is correct |
17 |
Correct |
64 ms |
1048576 KB |
Output is correct |
18 |
Correct |
55 ms |
1048576 KB |
Output is correct |
19 |
Correct |
49 ms |
1048576 KB |
Output is correct |
20 |
Correct |
51 ms |
1048576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1048576 KB |
Output is correct |
2 |
Correct |
4 ms |
1048576 KB |
Output is correct |
3 |
Execution timed out |
1161 ms |
1048576 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
1048576 KB |
Output is correct |
2 |
Correct |
92 ms |
1048576 KB |
Output is correct |
3 |
Execution timed out |
1135 ms |
1048576 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1118 ms |
1048576 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1118 ms |
1048576 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |