#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#define pii pair<int,int>
using namespace std;
struct Edge{
int a, b, c;
bool operator<(const Edge &p)const{
return c<p.c;
}
}w[301000];
int n, m, UF[301000], SZ[301000];
long long Res[301000];
vector<pii>TP[20];
int Find(int a){
if(a==UF[a])return a;
return Find(UF[a]);
}
bool Merge(int a, int b, int dep){
a = Find(a), b = Find(b);
if(a == b)return false;
TP[dep].push_back(pii(a,SZ[a]));
TP[dep].push_back(pii(b,SZ[b]));
if(SZ[a] < SZ[b])swap(a,b);
SZ[a] += SZ[b];
UF[b] = a;
return true;
}
void init(int dep){
int i;
for(i=TP[dep].size()-1;i>=0;i--){
UF[TP[dep][i].first] = TP[dep][i].first;
SZ[TP[dep][i].first] = TP[dep][i].second;
}
TP[dep].clear();
}
int chk[301000];
void Do(int b, int e, vector<Edge> &P, long long S, int dep){
if(b==e){
Res[b] += S;
return;
}
int i, j, m = (b+e)>>1;
for(i=0;i<P.size();i++){
if((P[i].a<=m&&P[i].a>=b) || (P[i].b<=m&&P[i].b>=b)){
Merge(P[i].a,P[i].b, dep);
}
}
for(i=0;i<P.size();i++){
if(Find(P[i].a)!=Find(P[i].b))chk[i] = 2;
else chk[i] = 0;
}
for(i=0;i<P.size();i++){
if(chk[i] == 2){
if(Merge(P[i].a,P[i].b, dep))chk[i] = 1;
}
}
init(dep);
for(i=0;i<P.size();i++){
if(chk[i] == 1)Merge(P[i].a,P[i].b,dep);
}
vector<Edge> T;
long long ss = 0;
for(i=0;i<P.size();i++){
if(chk[i] == 1)ss += P[i].c;
if(chk[i] == 0){
T.push_back(P[i]);
}
}
Do(b, m, T, S + ss, dep + 1);
init(dep);
for(i=0;i<P.size();i++){
if((P[i].a>m&&P[i].a<=e) || (P[i].b>m&&P[i].b<=e)){
Merge(P[i].a,P[i].b, dep);
}
}
for(i=0;i<P.size();i++){
if(Find(P[i].a)!=Find(P[i].b))chk[i] = 2;
else chk[i] = 0;
}
for(i=0;i<P.size();i++){
if(chk[i] == 2){
if(Merge(P[i].a,P[i].b, dep))chk[i] = 1;
}
}
init(dep);
for(i=0;i<P.size();i++){
if(chk[i] == 1)Merge(P[i].a,P[i].b, dep);
}
T.clear();
ss = 0;
for(i=0;i<P.size();i++){
if(chk[i] == 1)ss += P[i].c;
if(chk[i] == 0){
T.push_back(P[i]);
}
}
Do(m+1, e, T, S + ss, dep + 1);
init(dep);
}
int main(){
int i;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d%d",&w[i].a,&w[i].b,&w[i].c);
Res[w[i].a] += w[i].c;
Res[w[i].b] += w[i].c;
}
sort(w,w+m);
vector<Edge>P;
for(i=0;i<m;i++){
P.push_back(w[i]);
}
for(i=1;i<=n;i++)UF[i] = i;
Do(1,n,P,0,0);
for(i=1;i<=n;i++)printf("%lld\n",Res[i]);
}
Compilation message
LM.cpp: In function 'void Do(int, int, std::vector<Edge>&, long long int, int)':
LM.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:50:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:54:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:65:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:73:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:78:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:82:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:88:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:93:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<P.size();i++){
^
LM.cpp:44:12: warning: unused variable 'j' [-Wunused-variable]
int i, j, m = (b+e)>>1;
^
LM.cpp: In function 'int main()':
LM.cpp:104:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
LM.cpp:106:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&w[i].a,&w[i].b,&w[i].c);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
10896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
20900 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
