제출 #568823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568823		tqbfjotld	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	5079 ms	38508 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;

int p[505];
int rt(int a){return p[a]==a?a:p[a]=rt(p[a]);}
int A[100005];
int B[100005];
int W[100005];

int n;

struct node{
    int s,e;
    vector<int> usefulmin,usefulmax;
    node *l,*r;
    node (int _s, int _e){
        s = _s; e = _e;
        if (s!=e){
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
    }
    void construct(){
        for (int x = 1; x<=n; x++){
            p[x] = x;
        }
        for (int x = s; x<=e; x++){
            if (rt(A[x])!=rt(B[x])){
                usefulmin.push_back(x);
                p[rt(A[x])] = rt(B[x]);
            }
        }
        for (int x = 1; x<=n; x++){
            p[x] = x;
        }
        for (int x = e; x>=s; x--){
            if (rt(A[x])!=rt(B[x])){
                usefulmax.push_back(x);
                p[rt(A[x])] = rt(B[x]);
            }
        }
        if (s==e) return;
        l->construct();
        r->construct();
    }
    void qu(vector<int> &low, vector<int> &high, int val){
        //printf("qu %d-%d, %d,   %d %d\n",s,e,val,W[s],W[e]);
        if (W[s]>val){
            for (auto x : usefulmin){
                //printf("high add %d\n",x);
                high.push_back(x);
            }
            return;
        }
        if (W[e]<=val){
            for (auto x : usefulmax){
                //printf("low add %d\n",x);
                low.push_back(x);
            }
            return;
        }
        if (W[(s+e)/2]>=val){
            l->qu(low,high,val);
            r->qu(low,high,val);
        }
        else{
            r->qu(low,high,val);
            l->qu(low,high,val);
        }
    }
}*root;

int curval;
bool cmp1(int a, int b){
    return abs(W[a]-curval)<abs(W[b]-curval);
}

 main(){
    scanf("%d",&n);
    int m;
    scanf("%d",&m);
    vector<pair<int,pair<int,int>>> edgel;
    for (int x = 0; x<m; x++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edgel.push_back({c,{a,b}});
    }
    sort(edgel.begin(),edgel.end());
    for (int x = 0; x<m; x++){
        A[x] = edgel[x].second.first;
        B[x] = edgel[x].second.second;
        W[x] = edgel[x].first;
    }
    root = new node(0,m-1);
    root->construct();
    int q;
    scanf("%d",&q);
    while (q--){
        int v;
        scanf("%d",&v);
        vector<int> v1,v2;
        root->qu(v1,v2,v);
        //printf("qu fin\n");
        curval = v;
        sort(v1.begin(),v1.end(),cmp1);
        sort(v2.begin(),v2.end(),cmp1);
        int c1 = 0;
        int c2 = 0;
        long long ans = 0;
        for (int x = 1; x<=n; x++) p[x] = x;
        while (c1<v1.size() || c2<v2.size()){
            //printf("%d %d\n",c1,c2);
            if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
                if (rt(A[v1[c1]])!=rt(B[v1[c1]])){
                    ans += v-W[v1[c1]];
                    p[rt(A[v1[c1]])] = rt(B[v1[c1]]);
                }
                c1++;
            }
            else{
                if (rt(A[v2[c2]])!=rt(B[v2[c2]])){
                    ans += W[v2[c2]]-v;
                    p[rt(A[v2[c2]])] = rt(B[v2[c2]]);
                }
                c2++;
            }
        }
        printf("%lld\n",ans);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp:78:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 |  main(){
      |  ^~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         while (c1<v1.size() || c2<v2.size()){
      |                ~~^~~~~~~~~~
reconstruction.cpp:111:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         while (c1<v1.size() || c2<v2.size()){
      |                                ~~^~~~~~~~~~
reconstruction.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
      |                 ~~^~~~~~~~~~~
reconstruction.cpp:113:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
      |                                  ~~^~~~~~~~~~
reconstruction.cpp:113:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  113 |             if (c2==v2.size() || c1<v1.size() && v-W[v1[c1]]<W[v2[c2]]-v){
      |                                  ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
reconstruction.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
reconstruction.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
reconstruction.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d",&v);
      |         ~~~~~^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23