Submission #596815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
596815	2022-07-15T06:21:12 Z	조영욱(#8449)	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	299 ms	17556 KB

reconstruction

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

int n,m;
typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,int> Pi;
iP edge[100000];
bool use[100000];
priority_queue<P,vector<P>,greater<P>> pq1;
priority_queue<P,vector<P>,greater<P>> er;
priority_queue<P> pq2;
set<int> s;

int p[500];

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[b]=a;
}

vector<int> vec[500];
int arr[500];
vector<iP> ch;

int main(void) {
    scanf("%d %d",&n,&m);
    long long a=0;
    long long b=0;
    for(int i=0;i<n-1;i++) {
        arr[i]=1e9;
    }
    for(int i=0;i<m;i++) {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        u--;
        v--;
        vec[u].push_back(w);
    }
    for(int i=0;i<n-1;i++) {
        sort(vec[i].begin(),vec[i].end());
        for(int j=0;j+1<vec[i].size();j++) {
            ch.push_back(iP((vec[i][j]+vec[i][j+1]+1)/2,P(-2,vec[i][j]+vec[i][j+1])));
        }
        for(int j=0;j<vec[i].size();j++) {
            ch.push_back(iP(vec[i][j],P(2,-vec[i][j]*2)));
        }
        a--;
        b+=vec[i][0];
    }
//printf("%lld %lld\n",a,b);
    sort(ch.begin(),ch.end());
    int q;
    scanf("%d",&q);
    int ind=0;
    for(int i=0;i<q;i++) {
        int x;
        scanf("%d",&x);
        while (ind<ch.size()&&ch[ind].first<=x) {
            a+=ch[ind].second.first;
            b+=ch[ind].second.second;
            ind++;
        }
        printf("%lld\n",a*x+b);
    }
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j=0;j+1<vec[i].size();j++) {
      |                     ~~~^~~~~~~~~~~~~~
reconstruction.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
reconstruction.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while (ind<ch.size()&&ch[ind].first<=x) {
      |                ~~~^~~~~~~~~~
reconstruction.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
reconstruction.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d %d %d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
reconstruction.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	299 ms	16232 KB	Output is correct
5	Correct	278 ms	15376 KB	Output is correct
6	Correct	280 ms	15412 KB	Output is correct
7	Correct	286 ms	17360 KB	Output is correct
8	Correct	289 ms	17520 KB	Output is correct
9	Correct	293 ms	17488 KB	Output is correct
10	Correct	279 ms	15512 KB	Output is correct
11	Correct	292 ms	17556 KB	Output is correct