oj.uz

답안 #22694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22694 2017-04-30T06:37:04 Z ↓우리보다잘하는팀(#947, ainta, gs12117, gs13068) Logistical Metropolis (KRIII5_LM) C++
0 / 7
 2000 ms 20900 KB 
#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);
                                                ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 10896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 20900 KB Execution timed out
2 Halted 0 ms 0 KB -