oj.uz

Submission #713403

# Submission time Handle Problem Language Result Execution time Memory
713403 2023-03-21T22:59:02 Z urosk Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 1797 ms 34404 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 505
#define maxm 100005
struct edg{
    ll x,y,w;
};
ll n,m,q;
ll dsu[maxn];
ll root(ll x){
    while(x!=dsu[x]){
        dsu[x] = dsu[dsu[x]];
        x = dsu[x];
    }
    return x;
}
ll get(ll x,ll y){return root(x)==root(y);}
void upd(ll x,ll y){
    x = root(x);
    y = root(y);
    dsu[x] = y;
}
bool cmp(edg a,edg b){return a.w<b.w;}
bool cmp2(edg a,edg b){return a.x<b.x;}
edg e[maxm];
vector<edg> v;
void tc(){
    cin >> n >> m;
    for(ll i = 1;i<=m;i++){
        cin >> e[i].x >> e[i].y >> e[i].w;
    }
    sort(e+1,e+1+m,cmp);
    for(ll i = 1;i<=m;i++){
        iota(dsu+1,dsu+1+n,1);
        ll l = -1,r = -1;
        for(ll j = i+1;j<=m;j++){
            upd(e[j].x,e[j].y);
            if(get(e[i].x,e[i].y)){r = j;break;}
        }
        iota(dsu+1,dsu+1+n,1);
        for(ll j = i-1;j>=1;j--){
            upd(e[j].x,e[j].y);
            if(get(e[i].x,e[i].y)){l = j;break;}
        }
        ll lx,rx;
        if(r!=-1) rx = e[i].w + (e[r].w-e[i].w+1)/2;
        else rx = llinf;
        if(l!=-1) lx = e[l].w + (e[i].w-e[l].w+1)/2;
        else lx = -1;
        v.pb({lx,-1,e[i].w});
        v.pb({e[i].w,2,-2*e[i].w});
        v.pb({rx,-1,e[i].w});
    }
    sort(all(v),cmp2);
    ll j = 0;
    cin >> q;
    ll a = 0,b = 0;
    ///a*x+b
    for(ll i = 1;i<=q;i++){
        ll x; cin >> x;
        while(j<v.size()&&v[j].x<=x){
            a+=v[j].y;
            b+=v[j].w;
            j++;
        }
        cout<<a*x+b<<endl;
    }

}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}
/**
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17
**/

Compilation message

reconstruction.cpp: In function 'void tc()':
reconstruction.cpp:105:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         while(j<v.size()&&v[j].x<=x){
      |               ~^~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 324 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 324 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1618 ms 16824 KB Output is correct
21 Correct 1014 ms 16900 KB Output is correct
22 Correct 1076 ms 16800 KB Output is correct
23 Correct 1139 ms 16960 KB Output is correct
24 Correct 1386 ms 16868 KB Output is correct
25 Correct 1688 ms 16748 KB Output is correct
26 Correct 1618 ms 16724 KB Output is correct
27 Correct 1583 ms 16740 KB Output is correct
28 Correct 1575 ms 16756 KB Output is correct
29 Correct 1569 ms 16776 KB Output is correct
30 Correct 1608 ms 16904 KB Output is correct
31 Correct 1574 ms 16860 KB Output is correct
32 Correct 1595 ms 16868 KB Output is correct
33 Correct 1603 ms 16896 KB Output is correct
34 Correct 1574 ms 16904 KB Output is correct
35 Correct 1612 ms 16836 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1194 ms 32304 KB Output is correct
5 Correct 1221 ms 32392 KB Output is correct
6 Correct 1237 ms 32212 KB Output is correct
7 Correct 837 ms 34136 KB Output is correct
8 Correct 773 ms 34404 KB Output is correct
9 Correct 734 ms 34284 KB Output is correct
10 Correct 1207 ms 32452 KB Output is correct
11 Correct 809 ms 34392 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 324 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 206 ms 22400 KB Output is correct
21 Correct 202 ms 22612 KB Output is correct
22 Correct 227 ms 22436 KB Output is correct
23 Correct 213 ms 22468 KB Output is correct
24 Correct 205 ms 22380 KB Output is correct
25 Correct 189 ms 22352 KB Output is correct
26 Correct 193 ms 22368 KB Output is correct
27 Correct 180 ms 22524 KB Output is correct
28 Correct 197 ms 22428 KB Output is correct
29 Correct 191 ms 22496 KB Output is correct
30 Correct 190 ms 22572 KB Output is correct
31 Correct 221 ms 22328 KB Output is correct
32 Correct 195 ms 23024 KB Output is correct
33 Correct 193 ms 22316 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 324 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1618 ms 16824 KB Output is correct
21 Correct 1014 ms 16900 KB Output is correct
22 Correct 1076 ms 16800 KB Output is correct
23 Correct 1139 ms 16960 KB Output is correct
24 Correct 1386 ms 16868 KB Output is correct
25 Correct 1688 ms 16748 KB Output is correct
26 Correct 1618 ms 16724 KB Output is correct
27 Correct 1583 ms 16740 KB Output is correct
28 Correct 1575 ms 16756 KB Output is correct
29 Correct 1569 ms 16776 KB Output is correct
30 Correct 1608 ms 16904 KB Output is correct
31 Correct 1574 ms 16860 KB Output is correct
32 Correct 1595 ms 16868 KB Output is correct
33 Correct 1603 ms 16896 KB Output is correct
34 Correct 1574 ms 16904 KB Output is correct
35 Correct 1612 ms 16836 KB Output is correct
36 Correct 1589 ms 17024 KB Output is correct
37 Correct 977 ms 17012 KB Output is correct
38 Correct 1072 ms 17052 KB Output is correct
39 Correct 1095 ms 16968 KB Output is correct
40 Correct 1340 ms 17188 KB Output is correct
41 Correct 1646 ms 16996 KB Output is correct
42 Correct 1566 ms 17096 KB Output is correct
43 Correct 1559 ms 17076 KB Output is correct
44 Correct 1540 ms 17240 KB Output is correct
45 Correct 1537 ms 17104 KB Output is correct
46 Correct 1569 ms 17080 KB Output is correct
47 Correct 1550 ms 16936 KB Output is correct
48 Correct 1562 ms 17208 KB Output is correct
49 Correct 1571 ms 17072 KB Output is correct
50 Correct 1547 ms 17252 KB Output is correct
51 Correct 1554 ms 17168 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 324 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1618 ms 16824 KB Output is correct
21 Correct 1014 ms 16900 KB Output is correct
22 Correct 1076 ms 16800 KB Output is correct
23 Correct 1139 ms 16960 KB Output is correct
24 Correct 1386 ms 16868 KB Output is correct
25 Correct 1688 ms 16748 KB Output is correct
26 Correct 1618 ms 16724 KB Output is correct
27 Correct 1583 ms 16740 KB Output is correct
28 Correct 1575 ms 16756 KB Output is correct
29 Correct 1569 ms 16776 KB Output is correct
30 Correct 1608 ms 16904 KB Output is correct
31 Correct 1574 ms 16860 KB Output is correct
32 Correct 1595 ms 16868 KB Output is correct
33 Correct 1603 ms 16896 KB Output is correct
34 Correct 1574 ms 16904 KB Output is correct
35 Correct 1612 ms 16836 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1194 ms 32304 KB Output is correct
40 Correct 1221 ms 32392 KB Output is correct
41 Correct 1237 ms 32212 KB Output is correct
42 Correct 837 ms 34136 KB Output is correct
43 Correct 773 ms 34404 KB Output is correct
44 Correct 734 ms 34284 KB Output is correct
45 Correct 1207 ms 32452 KB Output is correct
46 Correct 809 ms 34392 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 206 ms 22400 KB Output is correct
49 Correct 202 ms 22612 KB Output is correct
50 Correct 227 ms 22436 KB Output is correct
51 Correct 213 ms 22468 KB Output is correct
52 Correct 205 ms 22380 KB Output is correct
53 Correct 189 ms 22352 KB Output is correct
54 Correct 193 ms 22368 KB Output is correct
55 Correct 180 ms 22524 KB Output is correct
56 Correct 197 ms 22428 KB Output is correct
57 Correct 191 ms 22496 KB Output is correct
58 Correct 190 ms 22572 KB Output is correct
59 Correct 221 ms 22328 KB Output is correct
60 Correct 195 ms 23024 KB Output is correct
61 Correct 193 ms 22316 KB Output is correct
62 Correct 1589 ms 17024 KB Output is correct
63 Correct 977 ms 17012 KB Output is correct
64 Correct 1072 ms 17052 KB Output is correct
65 Correct 1095 ms 16968 KB Output is correct
66 Correct 1340 ms 17188 KB Output is correct
67 Correct 1646 ms 16996 KB Output is correct
68 Correct 1566 ms 17096 KB Output is correct
69 Correct 1559 ms 17076 KB Output is correct
70 Correct 1540 ms 17240 KB Output is correct
71 Correct 1537 ms 17104 KB Output is correct
72 Correct 1569 ms 17080 KB Output is correct
73 Correct 1550 ms 16936 KB Output is correct
74 Correct 1562 ms 17208 KB Output is correct
75 Correct 1571 ms 17072 KB Output is correct
76 Correct 1547 ms 17252 KB Output is correct
77 Correct 1554 ms 17168 KB Output is correct
78 Correct 1732 ms 31540 KB Output is correct
79 Correct 1140 ms 33356 KB Output is correct
80 Correct 1185 ms 32336 KB Output is correct
81 Correct 1312 ms 32456 KB Output is correct
82 Correct 1506 ms 31472 KB Output is correct
83 Correct 1797 ms 31588 KB Output is correct
84 Correct 1750 ms 31408 KB Output is correct
85 Correct 1737 ms 31440 KB Output is correct
86 Correct 1708 ms 31516 KB Output is correct
87 Correct 1685 ms 33048 KB Output is correct
88 Correct 1713 ms 31308 KB Output is correct
89 Correct 1713 ms 31304 KB Output is correct
90 Correct 1714 ms 31624 KB Output is correct
91 Correct 1698 ms 31324 KB Output is correct
92 Correct 1701 ms 34088 KB Output is correct
93 Correct 1707 ms 32312 KB Output is correct