oj.uz

Submission #568842

# Submission time Handle Problem Language Result Execution time Memory
568842 2022-05-26T09:09:38 Z zaneyu Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 1381 ms 37372 KB 
/*input
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
1 3
1 4
4 6
1 10
5 8
1 10
7 1000000000
9 1000000000
11 1000000000
11 1000000000
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=5e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
struct segt{
    ll seg[4*maxn],lazy[4*maxn];
    int n;
    void resize(int _n){
        n=_n;
    } 
    inline void pushdown(int idx,int l,int r){
        if(!lazy[idx]) return;
        if(l==r){
            lazy[idx]=0;
            return;
        }
        int mid=l+r>>1;
        seg[idx<<1]+=lazy[idx]*(mid-l+1);
        seg[idx<<1|1]+=lazy[idx]*(r-mid);
        lazy[idx<<1]+=lazy[idx];
        lazy[idx<<1|1]+=lazy[idx];
        lazy[idx]=0;
    }
    inline void upd(int idx,int l,int r,int ql,int qr,ll x){
        if(ql<=l and r<=qr){
            lazy[idx]+=x;
            seg[idx]+=x*(r-l+1);
            pushdown(idx,l,r);
            return;
        }
        pushdown(idx,l,r);
        int mid=l+r>>1;
        if(qr<=mid) upd(idx<<1,l,mid,ql,qr,x);
        else if(ql>mid) upd(idx<<1|1,mid+1,r,ql,qr,x);
        else upd(idx<<1,l,mid,ql,qr,x),upd(idx<<1|1,mid+1,r,ql,qr,x);
        seg[idx]=(seg[idx<<1]+seg[idx<<1|1]);
    }
    inline ll query(int idx,int l,int r,int ql,int qr){
        pushdown(idx,l,r);
        if(ql<=l and r<=qr) return seg[idx];
        int mid=l+r>>1;
        if(qr<=mid) return query(idx<<1,l,mid,ql,qr);
        else if(ql>mid) return query(idx<<1|1,mid+1,r,ql,qr);
        return query(idx<<1,l,mid,ql,qr)+query(idx<<1|1,mid+1,r,ql,qr);
    }
    inline ll query(int l,int r){
        if(l>r) return 0;
        return query(1,0,n-1,l,r);
    }
    inline void upd(int l,int r,ll x){
        if(l>r) return;
        upd(1,0,n-1,l,r,x);
    }
}seg;
vector<pii> v[maxn];
pii mn[maxn];
int l[maxn],r[maxn];
vector<pair<int,pii>> ed;
void dfs(int u,int p){
    for(auto x:v[u]){
        if(x.f==p) continue;
        MNTO(mn[x.f],mn[u]);
        MNTO(mn[x.f],make_pair(ed[x.s].f,x.s));
        dfs(x.f,u);
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;
    cin>>n>>m;
    REP(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        ed.pb({c,{a,b}});
    }
    sort(ALL(ed));
    vector<pair<int,pii>> turn;
    REP(asd,m){
        auto x=ed[asd];
        int a=x.s.f,b=x.s.s;
        REP(i,n) mn[i]={INF,INF};
        dfs(a,-1);
        v[a].pb({b,asd}),v[b].pb({a,asd});
        pii z=mn[b];
        if(z.f==INF){
            l[asd]=1;
            continue;
        }
        int mid=(z.f+x.f+1)/2;
        r[z.s]=mid-1;
        l[asd]=mid;
        a=ed[z.s].s.f,b=ed[z.s].s.s;
        v[a].erase(find(ALL(v[a]),make_pair(b,z.s)));
        v[b].erase(find(ALL(v[b]),make_pair(a,z.s)));
    }
    REP(i,m){
        if(!r[i]) r[i]=1e9;
        //cout<<l[i]<<' '<<r[i]<<'\n';
        turn.pb({l[i],{-1,ed[i].f}});
        turn.pb({ed[i].f,{2,-2*ed[i].f}});
        turn.pb({r[i]+1,{-1,ed[i].f}});
    }
    sort(ALL(turn));
    int q;
    cin>>q;
    ll co=0,s=0;
    int p=0;
    while(q--){
        int k;
        cin>>k;
        while(p<sz(turn) and turn[p].f<=k){
            co+=turn[p].s.f;
            s+=turn[p].s.s;
            ++p;
        }
        cout<<s+co*k<<'\n';
    }
}

Compilation message

reconstruction.cpp: In member function 'void segt::pushdown(int, int, int)':
reconstruction.cpp:100:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mid=l+r>>1;
      |                 ~^~
reconstruction.cpp: In member function 'void segt::upd(int, int, int, int, int, ll)':
reconstruction.cpp:115:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |         int mid=l+r>>1;
      |                 ~^~
reconstruction.cpp: In member function 'll segt::query(int, int, int, int, int)':
reconstruction.cpp:124:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 8 ms 12092 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11992 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12084 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 6 ms 12088 KB Output is correct
18 Correct 6 ms 12084 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 8 ms 12092 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11992 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12084 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 6 ms 12088 KB Output is correct
18 Correct 6 ms 12084 KB Output is correct
19 Correct 6 ms 12088 KB Output is correct
20 Correct 1054 ms 21412 KB Output is correct
21 Correct 559 ms 21368 KB Output is correct
22 Correct 824 ms 21212 KB Output is correct
23 Correct 928 ms 21368 KB Output is correct
24 Correct 982 ms 21276 KB Output is correct
25 Correct 1052 ms 21260 KB Output is correct
26 Correct 1076 ms 21296 KB Output is correct
27 Correct 1077 ms 21324 KB Output is correct
28 Correct 1133 ms 21284 KB Output is correct
29 Correct 687 ms 21484 KB Output is correct
30 Correct 1051 ms 21208 KB Output is correct
31 Correct 1065 ms 21448 KB Output is correct
32 Correct 1038 ms 21272 KB Output is correct
33 Correct 1073 ms 21364 KB Output is correct
34 Correct 593 ms 22384 KB Output is correct
35 Correct 1028 ms 21284 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12088 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 1162 ms 28744 KB Output is correct
5 Correct 1082 ms 28728 KB Output is correct
6 Correct 1083 ms 28720 KB Output is correct
7 Correct 287 ms 30636 KB Output is correct
8 Correct 272 ms 30752 KB Output is correct
9 Correct 287 ms 30772 KB Output is correct
10 Correct 1088 ms 28824 KB Output is correct
11 Correct 290 ms 30736 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 8 ms 12092 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11992 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12084 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 6 ms 12088 KB Output is correct
18 Correct 6 ms 12084 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 208 ms 25304 KB Output is correct
21 Correct 181 ms 25148 KB Output is correct
22 Correct 208 ms 25004 KB Output is correct
23 Correct 193 ms 25124 KB Output is correct
24 Correct 207 ms 24980 KB Output is correct
25 Correct 211 ms 24932 KB Output is correct
26 Correct 188 ms 24908 KB Output is correct
27 Correct 192 ms 25028 KB Output is correct
28 Correct 185 ms 24972 KB Output is correct
29 Correct 200 ms 24980 KB Output is correct
30 Correct 188 ms 24936 KB Output is correct
31 Correct 193 ms 24976 KB Output is correct
32 Correct 184 ms 25516 KB Output is correct
33 Correct 189 ms 24772 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 8 ms 12092 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11992 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12084 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 6 ms 12088 KB Output is correct
18 Correct 6 ms 12084 KB Output is correct
19 Correct 6 ms 12088 KB Output is correct
20 Correct 1054 ms 21412 KB Output is correct
21 Correct 559 ms 21368 KB Output is correct
22 Correct 824 ms 21212 KB Output is correct
23 Correct 928 ms 21368 KB Output is correct
24 Correct 982 ms 21276 KB Output is correct
25 Correct 1052 ms 21260 KB Output is correct
26 Correct 1076 ms 21296 KB Output is correct
27 Correct 1077 ms 21324 KB Output is correct
28 Correct 1133 ms 21284 KB Output is correct
29 Correct 687 ms 21484 KB Output is correct
30 Correct 1051 ms 21208 KB Output is correct
31 Correct 1065 ms 21448 KB Output is correct
32 Correct 1038 ms 21272 KB Output is correct
33 Correct 1073 ms 21364 KB Output is correct
34 Correct 593 ms 22384 KB Output is correct
35 Correct 1028 ms 21284 KB Output is correct
36 Correct 1041 ms 21236 KB Output is correct
37 Correct 516 ms 21292 KB Output is correct
38 Correct 864 ms 21232 KB Output is correct
39 Correct 917 ms 21512 KB Output is correct
40 Correct 999 ms 21220 KB Output is correct
41 Correct 1031 ms 21324 KB Output is correct
42 Correct 1036 ms 21220 KB Output is correct
43 Correct 1033 ms 21304 KB Output is correct
44 Correct 1085 ms 21184 KB Output is correct
45 Correct 648 ms 21468 KB Output is correct
46 Correct 1031 ms 21304 KB Output is correct
47 Correct 1002 ms 21284 KB Output is correct
48 Correct 1025 ms 21228 KB Output is correct
49 Correct 1073 ms 21144 KB Output is correct
50 Correct 571 ms 22508 KB Output is correct
51 Correct 1107 ms 21156 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 8 ms 12092 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11992 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 7 ms 12084 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 11988 KB Output is correct
16 Correct 7 ms 11988 KB Output is correct
17 Correct 6 ms 12088 KB Output is correct
18 Correct 6 ms 12084 KB Output is correct
19 Correct 6 ms 12088 KB Output is correct
20 Correct 1054 ms 21412 KB Output is correct
21 Correct 559 ms 21368 KB Output is correct
22 Correct 824 ms 21212 KB Output is correct
23 Correct 928 ms 21368 KB Output is correct
24 Correct 982 ms 21276 KB Output is correct
25 Correct 1052 ms 21260 KB Output is correct
26 Correct 1076 ms 21296 KB Output is correct
27 Correct 1077 ms 21324 KB Output is correct
28 Correct 1133 ms 21284 KB Output is correct
29 Correct 687 ms 21484 KB Output is correct
30 Correct 1051 ms 21208 KB Output is correct
31 Correct 1065 ms 21448 KB Output is correct
32 Correct 1038 ms 21272 KB Output is correct
33 Correct 1073 ms 21364 KB Output is correct
34 Correct 593 ms 22384 KB Output is correct
35 Correct 1028 ms 21284 KB Output is correct
36 Correct 7 ms 11988 KB Output is correct
37 Correct 7 ms 12088 KB Output is correct
38 Correct 7 ms 11988 KB Output is correct
39 Correct 1162 ms 28744 KB Output is correct
40 Correct 1082 ms 28728 KB Output is correct
41 Correct 1083 ms 28720 KB Output is correct
42 Correct 287 ms 30636 KB Output is correct
43 Correct 272 ms 30752 KB Output is correct
44 Correct 287 ms 30772 KB Output is correct
45 Correct 1088 ms 28824 KB Output is correct
46 Correct 290 ms 30736 KB Output is correct
47 Correct 6 ms 11988 KB Output is correct
48 Correct 208 ms 25304 KB Output is correct
49 Correct 181 ms 25148 KB Output is correct
50 Correct 208 ms 25004 KB Output is correct
51 Correct 193 ms 25124 KB Output is correct
52 Correct 207 ms 24980 KB Output is correct
53 Correct 211 ms 24932 KB Output is correct
54 Correct 188 ms 24908 KB Output is correct
55 Correct 192 ms 25028 KB Output is correct
56 Correct 185 ms 24972 KB Output is correct
57 Correct 200 ms 24980 KB Output is correct
58 Correct 188 ms 24936 KB Output is correct
59 Correct 193 ms 24976 KB Output is correct
60 Correct 184 ms 25516 KB Output is correct
61 Correct 189 ms 24772 KB Output is correct
62 Correct 1041 ms 21236 KB Output is correct
63 Correct 516 ms 21292 KB Output is correct
64 Correct 864 ms 21232 KB Output is correct
65 Correct 917 ms 21512 KB Output is correct
66 Correct 999 ms 21220 KB Output is correct
67 Correct 1031 ms 21324 KB Output is correct
68 Correct 1036 ms 21220 KB Output is correct
69 Correct 1033 ms 21304 KB Output is correct
70 Correct 1085 ms 21184 KB Output is correct
71 Correct 648 ms 21468 KB Output is correct
72 Correct 1031 ms 21304 KB Output is correct
73 Correct 1002 ms 21284 KB Output is correct
74 Correct 1025 ms 21228 KB Output is correct
75 Correct 1073 ms 21144 KB Output is correct
76 Correct 571 ms 22508 KB Output is correct
77 Correct 1107 ms 21156 KB Output is correct
78 Correct 1314 ms 35364 KB Output is correct
79 Correct 772 ms 37372 KB Output is correct
80 Correct 1141 ms 36372 KB Output is correct
81 Correct 1207 ms 36324 KB Output is correct
82 Correct 1259 ms 35476 KB Output is correct
83 Correct 1288 ms 35272 KB Output is correct
84 Correct 1346 ms 35360 KB Output is correct
85 Correct 1348 ms 35320 KB Output is correct
86 Correct 1329 ms 27760 KB Output is correct
87 Correct 925 ms 33756 KB Output is correct
88 Correct 1381 ms 35396 KB Output is correct
89 Correct 1354 ms 35388 KB Output is correct
90 Correct 1304 ms 35376 KB Output is correct
91 Correct 1285 ms 31580 KB Output is correct
92 Correct 699 ms 31676 KB Output is correct
93 Correct 1251 ms 29916 KB Output is correct