# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
5368 |
2014-04-16T07:55:35 Z |
baneling100 |
비용 (KOI11_cost) |
C++ |
|
1500 ms |
9496 KB |
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair <int,int> ppair;
queue <int> q;
pair <int,ppair> edge[100001];
vector <ppair> a[100001];
int n, m, check[100001], visit[100001];
long long ans;
void input(void)
{
int i, x, y, w;
scanf("%d %d",&n,&m);
for(i=1 ; i<=m ; i++)
{
scanf("%d %d %d",&x,&y,&w);
edge[i]=make_pair(w,make_pair(x,y));
}
sort(edge+1,edge+m+1);
for(i=1 ; i<=m ; i++)
{
a[edge[i].second.first].push_back(make_pair(edge[i].second.second,i));
a[edge[i].second.second].push_back(make_pair(edge[i].second.first,i));
}
}
int bfs(int start)
{
int i, j, now, cnt=0;
for(i=1 ; i<=n ; i++)
visit[i]=0;
q.push(start);
visit[start]=1;
cnt++;
while(!q.empty())
{
now=q.front();
q.pop();
j=a[now].size();
for(i=0 ; i<j ; i++)
if(visit[a[now][i].first]==0 && check[a[now][i].second]==0)
{
q.push(a[now][i].first);
visit[a[now][i].first]=1;
cnt++;
}
}
return cnt;
}
void process(void)
{
int i, x, y, hab=0;
for(i=1 ; i<=m ; i++)
{
hab+=edge[i].first;
check[i]=1;
x=bfs(edge[i].second.first);
if(visit[edge[i].second.second]==0)
{
y=bfs(edge[i].second.second);
ans+=(long long)x*y*hab;
ans%=1000000000;
}
}
}
void output(void)
{
printf("%lld",ans);
}
int main(void)
{
input();
process();
output();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5540 KB |
Output is correct |
2 |
Correct |
0 ms |
5540 KB |
Output is correct |
3 |
Correct |
0 ms |
5540 KB |
Output is correct |
4 |
Correct |
0 ms |
5540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
5540 KB |
Output is correct |
2 |
Correct |
4 ms |
5540 KB |
Output is correct |
3 |
Correct |
60 ms |
5540 KB |
Output is correct |
4 |
Correct |
64 ms |
5540 KB |
Output is correct |
5 |
Correct |
288 ms |
5672 KB |
Output is correct |
6 |
Execution timed out |
1500 ms |
5804 KB |
Program timed out |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1500 ms |
6196 KB |
Program timed out |
2 |
Execution timed out |
1500 ms |
6988 KB |
Program timed out |
3 |
Execution timed out |
1500 ms |
8176 KB |
Program timed out |
4 |
Execution timed out |
1500 ms |
6196 KB |
Program timed out |
5 |
Execution timed out |
1500 ms |
8308 KB |
Program timed out |
6 |
Execution timed out |
1500 ms |
7384 KB |
Program timed out |
7 |
Execution timed out |
1500 ms |
8440 KB |
Program timed out |
8 |
Execution timed out |
1500 ms |
8572 KB |
Program timed out |
9 |
Execution timed out |
1500 ms |
9496 KB |
Program timed out |
10 |
Execution timed out |
1500 ms |
8440 KB |
Program timed out |