Submission #22672

#	Time	Username	Problem	Language	Result	Execution time	Memory
22672		↓우리보다잘하는팀 (#40)	Logistical Metropolis (KRIII5_LM)	C++98	2 / 7	2000 ms	20020 KiB

LM

#include<cstdio>
#include<algorithm>
#include<vector>
#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]));
    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();
}
bool 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(Merge(P[i].a,P[i].b, dep))chk[i] = true;
        else chk[i] = false;
    }
    init(dep);
    for(i=0;i<P.size();i++){
        if(chk[i])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])ss += P[i].c;
        if(Find(P[i].a) != Find(P[i].b)){
            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(Merge(P[i].a,P[i].b, dep))chk[i] = true;
        else chk[i] = false;
    }
    init(dep);
    for(i=0;i<P.size();i++){
        if(chk[i])Merge(P[i].a,P[i].b, dep);
    }
    T.clear();
    ss = 0;
    for(i=0;i<P.size();i++){
        if(chk[i])ss += P[i].c;
        if(Find(P[i].a) != Find(P[i].b)){
            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 (stderr)

LM.cpp: In function 'void Do(int, int, std::vector<Edge>&, long long int, int)':
LM.cpp:43:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:53:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:58:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:66:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:71:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:81:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<P.size();i++){
              ^
LM.cpp:42:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, m = (b+e)>>1;
            ^
LM.cpp: In function 'int main()':
LM.cpp:92: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:94: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);
                                                ^

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5