oj.uz

Submission #22672

# Submission time Handle Problem Language Result Execution time Memory
22672 2017-04-30T06:23:59 Z ↓우리보다잘하는팀(#947, ainta, gs12117, gs13068) Logistical Metropolis (KRIII5_LM) C++
2 / 7
 2000 ms 20020 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 10328 KB Output is correct
2 Correct 603 ms 10304 KB Output is correct
3 Correct 533 ms 10304 KB Output is correct
4 Correct 573 ms 10328 KB Output is correct
5 Correct 523 ms 10304 KB Output is correct
6 Correct 469 ms 10472 KB Output is correct
7 Correct 646 ms 10304 KB Output is correct
8 Correct 576 ms 10400 KB Output is correct
9 Correct 426 ms 10448 KB Output is correct
10 Correct 569 ms 10304 KB Output is correct
11 Correct 563 ms 10328 KB Output is correct
12 Correct 596 ms 10448 KB Output is correct
13 Correct 1949 ms 10544 KB Output is correct
14 Correct 996 ms 10552 KB Output is correct
15 Correct 1018 ms 10404 KB Output is correct
16 Correct 486 ms 10472 KB Output is correct
17 Correct 473 ms 10472 KB Output is correct
18 Correct 479 ms 10464 KB Output is correct
19 Correct 483 ms 10464 KB Output is correct
20 Correct 483 ms 10492 KB Output is correct
21 Correct 499 ms 10504 KB Output is correct
22 Correct 469 ms 10472 KB Output is correct
23 Correct 496 ms 10468 KB Output is correct
24 Correct 446 ms 10468 KB Output is correct
25 Correct 0 ms 9700 KB Output is correct
26 Correct 0 ms 9700 KB Output is correct
27 Correct 0 ms 9700 KB Output is correct
28 Correct 6 ms 9836 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 20020 KB Execution timed out
2 Halted 0 ms 0 KB -