oj.uz

Submission #750897

# Submission time Handle Problem Language Result Execution time Memory
750897 2023-05-30T13:04:41 Z edogawa_something Vinjete (COI22_vinjete) C++17
69 / 100
 433 ms 413272 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef bool bl;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef vector<pii> vpi;
#define ordered_set tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0);cin.tie();
#define test ll qqqqq;cin>>qqqqq;while(qqqqq--)
#define test1 ll qqqqq=1;while(qqqqq--)
#define F first
#define S second
#define forn(i,n) for(int i=0;i<n;i++)
#define forx(i,j,n) for(int i=j;i<n;i++)
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define pow powww
#define prtll(x) printf("%lld",x)
#define prtld(x) printf("%Lf",x)
#define prtst(x) printf("%s",x)
#define prtch(x) printf("%c",x)
#define measure chrono::high_resolution_clock::now()
#define duration chrono::duration_cast<chrono::milliseconds>(end-start)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const ll dx[]{1,0,-1,0,1,-1,1,-1};
const ll dy[]{0,-1,0,1,1,-1,-1,1};
const ll inf=1e18;
const ll mod=1e9+7;
const ll LM=1e8+1;
const ll M=3e6+10;
const ll MM=4002;
const ll MMM=501;
const ld pi=acos(-1);
//const ll mod=998244353;
ll pow(ll r,ll to,ll m=mod){
  ll res=1;
  r%=m;
  while(to){
    if((to&1)){
      res*=r,res%=m;
    }
    r*=r,r%=m;
    to=(to>>1);
  }
  return res;
}
ll le[M],ri[M],val[M],cnt[M],has[M],t=1;
ll n,m,a[M];
struct seg{
  void update(ll l,ll r,ll v,ll x,ll lx,ll rx){
    if(rx<=l||r<=lx)
    return;
    if(rx-lx==1){
      val[x]+=v;
      cnt[x]=1;
      return;
    }
    if(rx<=r&&lx>=l){
      has[x]+=v;
      return;
    }
    else{
      ll mid=((lx+rx)>>1);
      if(le[x]==0){
      le[x]=t++;
      cnt[le[x]]=mid-lx;
      }
      if(ri[x]==0){
      ri[x]=t++;
      cnt[ri[x]]=rx-mid;
      }
      update(l,r,v,le[x],lx,mid);
      update(l,r,v,ri[x],mid,rx);
      if(val[ri[x]]+has[ri[x]]==val[le[x]]+has[le[x]])
      cnt[x]=cnt[ri[x]]+cnt[le[x]];
      else if(val[ri[x]]+has[ri[x]]<val[le[x]]+has[le[x]])
      cnt[x]=cnt[ri[x]];
      else
      cnt[x]=cnt[le[x]];
      val[x]=min(val[le[x]]+has[le[x]],val[ri[x]]+has[ri[x]]);
    }
  }
  void update(ll l,ll r,ll v){
    update(l,r,v,0,0,(1<<30));
  }
  ll query(){
    return (1<<30)-cnt[0];
  }
}s;
vector<pair<ll,pii>>v[M];
ll ans[M];
void dfs(ll r,ll pa){
  ans[r]=s.query();
  for(auto it:v[r]){
    if(it.F==pa)
    continue;
    s.update(it.S.F,it.S.S,1);
    dfs(it.F,r);
    s.update(it.S.F,it.S.S,-1);
  }
}
int main(){
  fast
  //freopen("gen.txt","r",stdin);
  auto start=measure;
  test1{
    cin>>n>>m;
    forn(i,n-1){
      ll x,y,l,r;
      cin>>x>>y>>l>>r;
      v[x].pb({y,{l-1,r}});
      v[y].pb({x,{l-1,r}});
    }
    dfs(1,-1);
    forx(i,2,n+1){
      cout<<ans[i]<<'\n';
    }
  }
  auto end=measure;
  auto dur=duration;
  //cout<<fixed<<dur.count()<<'\n';
  return 0;
}
/*
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70984 KB Output is correct
2 Correct 37 ms 71016 KB Output is correct
3 Correct 35 ms 71088 KB Output is correct
4 Correct 39 ms 70988 KB Output is correct
5 Correct 35 ms 71100 KB Output is correct
6 Correct 37 ms 70996 KB Output is correct
7 Correct 36 ms 70796 KB Output is correct
8 Correct 35 ms 70856 KB Output is correct
9 Correct 38 ms 70868 KB Output is correct
10 Correct 40 ms 70916 KB Output is correct
11 Correct 36 ms 70964 KB Output is correct
12 Correct 37 ms 70860 KB Output is correct
13 Correct 36 ms 70924 KB Output is correct
14 Correct 37 ms 70860 KB Output is correct
15 Correct 37 ms 70756 KB Output is correct
16 Correct 35 ms 70752 KB Output is correct
17 Correct 36 ms 70864 KB Output is correct
18 Correct 36 ms 70828 KB Output is correct
19 Correct 45 ms 70920 KB Output is correct
20 Correct 42 ms 70864 KB Output is correct
21 Correct 38 ms 70888 KB Output is correct
22 Correct 36 ms 70908 KB Output is correct
23 Correct 35 ms 70828 KB Output is correct
24 Correct 36 ms 70832 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70984 KB Output is correct
2 Correct 37 ms 71016 KB Output is correct
3 Correct 35 ms 71088 KB Output is correct
4 Correct 39 ms 70988 KB Output is correct
5 Correct 35 ms 71100 KB Output is correct
6 Correct 37 ms 70996 KB Output is correct
7 Correct 36 ms 70796 KB Output is correct
8 Correct 35 ms 70856 KB Output is correct
9 Correct 38 ms 70868 KB Output is correct
10 Correct 40 ms 70916 KB Output is correct
11 Correct 36 ms 70964 KB Output is correct
12 Correct 37 ms 70860 KB Output is correct
13 Correct 36 ms 70924 KB Output is correct
14 Correct 37 ms 70860 KB Output is correct
15 Correct 37 ms 70756 KB Output is correct
16 Correct 35 ms 70752 KB Output is correct
17 Correct 36 ms 70864 KB Output is correct
18 Correct 36 ms 70828 KB Output is correct
19 Correct 45 ms 70920 KB Output is correct
20 Correct 42 ms 70864 KB Output is correct
21 Correct 38 ms 70888 KB Output is correct
22 Correct 36 ms 70908 KB Output is correct
23 Correct 35 ms 70828 KB Output is correct
24 Correct 36 ms 70832 KB Output is correct
25 Correct 38 ms 71044 KB Output is correct
26 Correct 36 ms 70988 KB Output is correct
27 Correct 38 ms 73812 KB Output is correct
28 Correct 39 ms 73756 KB Output is correct
29 Correct 38 ms 72208 KB Output is correct
30 Correct 38 ms 72396 KB Output is correct
31 Correct 45 ms 73732 KB Output is correct
32 Correct 50 ms 73776 KB Output is correct
33 Correct 39 ms 73748 KB Output is correct
34 Correct 38 ms 73804 KB Output is correct
35 Correct 36 ms 70860 KB Output is correct
36 Correct 38 ms 70860 KB Output is correct
37 Correct 39 ms 73628 KB Output is correct
38 Correct 41 ms 73736 KB Output is correct
39 Correct 40 ms 72040 KB Output is correct
40 Correct 40 ms 72208 KB Output is correct
41 Correct 50 ms 73636 KB Output is correct
42 Correct 41 ms 73612 KB Output is correct
43 Correct 36 ms 70916 KB Output is correct
44 Correct 44 ms 70904 KB Output is correct
45 Correct 41 ms 73644 KB Output is correct
46 Correct 45 ms 73624 KB Output is correct
47 Correct 36 ms 72036 KB Output is correct
48 Correct 36 ms 72016 KB Output is correct
49 Correct 38 ms 73676 KB Output is correct
50 Correct 38 ms 73684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70984 KB Output is correct
2 Correct 37 ms 71016 KB Output is correct
3 Correct 35 ms 71088 KB Output is correct
4 Correct 39 ms 70988 KB Output is correct
5 Correct 35 ms 71100 KB Output is correct
6 Correct 37 ms 70996 KB Output is correct
7 Correct 36 ms 70796 KB Output is correct
8 Correct 35 ms 70856 KB Output is correct
9 Correct 38 ms 70868 KB Output is correct
10 Correct 40 ms 70916 KB Output is correct
11 Correct 36 ms 70964 KB Output is correct
12 Correct 37 ms 70860 KB Output is correct
13 Correct 36 ms 70924 KB Output is correct
14 Correct 37 ms 70860 KB Output is correct
15 Correct 37 ms 70756 KB Output is correct
16 Correct 35 ms 70752 KB Output is correct
17 Correct 36 ms 70864 KB Output is correct
18 Correct 36 ms 70828 KB Output is correct
19 Correct 45 ms 70920 KB Output is correct
20 Correct 42 ms 70864 KB Output is correct
21 Correct 38 ms 70888 KB Output is correct
22 Correct 36 ms 70908 KB Output is correct
23 Correct 35 ms 70828 KB Output is correct
24 Correct 36 ms 70832 KB Output is correct
25 Correct 89 ms 79544 KB Output is correct
26 Correct 104 ms 79460 KB Output is correct
27 Correct 106 ms 82312 KB Output is correct
28 Correct 104 ms 82376 KB Output is correct
29 Correct 91 ms 81820 KB Output is correct
30 Correct 87 ms 81904 KB Output is correct
31 Correct 41 ms 73292 KB Output is correct
32 Correct 41 ms 73292 KB Output is correct
33 Correct 41 ms 73292 KB Output is correct
34 Correct 42 ms 73336 KB Output is correct
35 Correct 88 ms 74472 KB Output is correct
36 Correct 92 ms 74796 KB Output is correct
37 Correct 107 ms 77384 KB Output is correct
38 Correct 117 ms 77656 KB Output is correct
39 Correct 104 ms 76968 KB Output is correct
40 Correct 89 ms 76728 KB Output is correct
41 Correct 42 ms 72744 KB Output is correct
42 Correct 42 ms 72748 KB Output is correct
43 Correct 92 ms 73940 KB Output is correct
44 Correct 86 ms 73996 KB Output is correct
45 Correct 107 ms 76824 KB Output is correct
46 Correct 106 ms 76752 KB Output is correct
47 Correct 104 ms 76132 KB Output is correct
48 Correct 110 ms 76332 KB Output is correct
49 Correct 45 ms 72732 KB Output is correct
50 Correct 50 ms 72608 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70984 KB Output is correct
2 Correct 37 ms 71016 KB Output is correct
3 Correct 35 ms 71088 KB Output is correct
4 Correct 39 ms 70988 KB Output is correct
5 Correct 35 ms 71100 KB Output is correct
6 Correct 37 ms 70996 KB Output is correct
7 Correct 36 ms 70796 KB Output is correct
8 Correct 35 ms 70856 KB Output is correct
9 Correct 38 ms 70868 KB Output is correct
10 Correct 40 ms 70916 KB Output is correct
11 Correct 36 ms 70964 KB Output is correct
12 Correct 37 ms 70860 KB Output is correct
13 Correct 36 ms 70924 KB Output is correct
14 Correct 37 ms 70860 KB Output is correct
15 Correct 37 ms 70756 KB Output is correct
16 Correct 35 ms 70752 KB Output is correct
17 Correct 36 ms 70864 KB Output is correct
18 Correct 36 ms 70828 KB Output is correct
19 Correct 45 ms 70920 KB Output is correct
20 Correct 42 ms 70864 KB Output is correct
21 Correct 38 ms 70888 KB Output is correct
22 Correct 36 ms 70908 KB Output is correct
23 Correct 35 ms 70828 KB Output is correct
24 Correct 36 ms 70832 KB Output is correct
25 Correct 89 ms 79544 KB Output is correct
26 Correct 104 ms 79460 KB Output is correct
27 Correct 106 ms 82312 KB Output is correct
28 Correct 104 ms 82376 KB Output is correct
29 Correct 91 ms 81820 KB Output is correct
30 Correct 87 ms 81904 KB Output is correct
31 Correct 41 ms 73292 KB Output is correct
32 Correct 41 ms 73292 KB Output is correct
33 Correct 41 ms 73292 KB Output is correct
34 Correct 42 ms 73336 KB Output is correct
35 Correct 88 ms 74472 KB Output is correct
36 Correct 92 ms 74796 KB Output is correct
37 Correct 107 ms 77384 KB Output is correct
38 Correct 117 ms 77656 KB Output is correct
39 Correct 104 ms 76968 KB Output is correct
40 Correct 89 ms 76728 KB Output is correct
41 Correct 42 ms 72744 KB Output is correct
42 Correct 42 ms 72748 KB Output is correct
43 Correct 92 ms 73940 KB Output is correct
44 Correct 86 ms 73996 KB Output is correct
45 Correct 107 ms 76824 KB Output is correct
46 Correct 106 ms 76752 KB Output is correct
47 Correct 104 ms 76132 KB Output is correct
48 Correct 110 ms 76332 KB Output is correct
49 Correct 45 ms 72732 KB Output is correct
50 Correct 50 ms 72608 KB Output is correct
51 Correct 163 ms 92668 KB Output is correct
52 Correct 180 ms 92732 KB Output is correct
53 Correct 279 ms 99808 KB Output is correct
54 Correct 242 ms 99748 KB Output is correct
55 Correct 167 ms 98508 KB Output is correct
56 Correct 181 ms 98404 KB Output is correct
57 Correct 57 ms 79776 KB Output is correct
58 Correct 66 ms 79816 KB Output is correct
59 Correct 58 ms 79736 KB Output is correct
60 Correct 61 ms 79872 KB Output is correct
61 Correct 170 ms 80596 KB Output is correct
62 Correct 169 ms 81000 KB Output is correct
63 Correct 274 ms 87252 KB Output is correct
64 Correct 249 ms 87508 KB Output is correct
65 Correct 196 ms 86460 KB Output is correct
66 Correct 175 ms 85992 KB Output is correct
67 Correct 66 ms 77228 KB Output is correct
68 Correct 59 ms 77220 KB Output is correct
69 Correct 254 ms 78960 KB Output is correct
70 Correct 210 ms 78816 KB Output is correct
71 Correct 297 ms 85964 KB Output is correct
72 Correct 297 ms 85912 KB Output is correct
73 Correct 192 ms 84252 KB Output is correct
74 Correct 203 ms 84368 KB Output is correct
75 Correct 75 ms 77012 KB Output is correct
76 Correct 75 ms 77060 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70984 KB Output is correct
2 Correct 37 ms 71016 KB Output is correct
3 Correct 35 ms 71088 KB Output is correct
4 Correct 39 ms 70988 KB Output is correct
5 Correct 35 ms 71100 KB Output is correct
6 Correct 37 ms 70996 KB Output is correct
7 Correct 36 ms 70796 KB Output is correct
8 Correct 35 ms 70856 KB Output is correct
9 Correct 38 ms 70868 KB Output is correct
10 Correct 40 ms 70916 KB Output is correct
11 Correct 36 ms 70964 KB Output is correct
12 Correct 37 ms 70860 KB Output is correct
13 Correct 36 ms 70924 KB Output is correct
14 Correct 37 ms 70860 KB Output is correct
15 Correct 37 ms 70756 KB Output is correct
16 Correct 35 ms 70752 KB Output is correct
17 Correct 36 ms 70864 KB Output is correct
18 Correct 36 ms 70828 KB Output is correct
19 Correct 45 ms 70920 KB Output is correct
20 Correct 42 ms 70864 KB Output is correct
21 Correct 38 ms 70888 KB Output is correct
22 Correct 36 ms 70908 KB Output is correct
23 Correct 35 ms 70828 KB Output is correct
24 Correct 36 ms 70832 KB Output is correct
25 Correct 38 ms 71044 KB Output is correct
26 Correct 36 ms 70988 KB Output is correct
27 Correct 38 ms 73812 KB Output is correct
28 Correct 39 ms 73756 KB Output is correct
29 Correct 38 ms 72208 KB Output is correct
30 Correct 38 ms 72396 KB Output is correct
31 Correct 45 ms 73732 KB Output is correct
32 Correct 50 ms 73776 KB Output is correct
33 Correct 39 ms 73748 KB Output is correct
34 Correct 38 ms 73804 KB Output is correct
35 Correct 36 ms 70860 KB Output is correct
36 Correct 38 ms 70860 KB Output is correct
37 Correct 39 ms 73628 KB Output is correct
38 Correct 41 ms 73736 KB Output is correct
39 Correct 40 ms 72040 KB Output is correct
40 Correct 40 ms 72208 KB Output is correct
41 Correct 50 ms 73636 KB Output is correct
42 Correct 41 ms 73612 KB Output is correct
43 Correct 36 ms 70916 KB Output is correct
44 Correct 44 ms 70904 KB Output is correct
45 Correct 41 ms 73644 KB Output is correct
46 Correct 45 ms 73624 KB Output is correct
47 Correct 36 ms 72036 KB Output is correct
48 Correct 36 ms 72016 KB Output is correct
49 Correct 38 ms 73676 KB Output is correct
50 Correct 38 ms 73684 KB Output is correct
51 Correct 89 ms 79544 KB Output is correct
52 Correct 104 ms 79460 KB Output is correct
53 Correct 106 ms 82312 KB Output is correct
54 Correct 104 ms 82376 KB Output is correct
55 Correct 91 ms 81820 KB Output is correct
56 Correct 87 ms 81904 KB Output is correct
57 Correct 41 ms 73292 KB Output is correct
58 Correct 41 ms 73292 KB Output is correct
59 Correct 41 ms 73292 KB Output is correct
60 Correct 42 ms 73336 KB Output is correct
61 Correct 88 ms 74472 KB Output is correct
62 Correct 92 ms 74796 KB Output is correct
63 Correct 107 ms 77384 KB Output is correct
64 Correct 117 ms 77656 KB Output is correct
65 Correct 104 ms 76968 KB Output is correct
66 Correct 89 ms 76728 KB Output is correct
67 Correct 42 ms 72744 KB Output is correct
68 Correct 42 ms 72748 KB Output is correct
69 Correct 92 ms 73940 KB Output is correct
70 Correct 86 ms 73996 KB Output is correct
71 Correct 107 ms 76824 KB Output is correct
72 Correct 106 ms 76752 KB Output is correct
73 Correct 104 ms 76132 KB Output is correct
74 Correct 110 ms 76332 KB Output is correct
75 Correct 45 ms 72732 KB Output is correct
76 Correct 50 ms 72608 KB Output is correct
77 Correct 163 ms 92668 KB Output is correct
78 Correct 180 ms 92732 KB Output is correct
79 Correct 279 ms 99808 KB Output is correct
80 Correct 242 ms 99748 KB Output is correct
81 Correct 167 ms 98508 KB Output is correct
82 Correct 181 ms 98404 KB Output is correct
83 Correct 57 ms 79776 KB Output is correct
84 Correct 66 ms 79816 KB Output is correct
85 Correct 58 ms 79736 KB Output is correct
86 Correct 61 ms 79872 KB Output is correct
87 Correct 170 ms 80596 KB Output is correct
88 Correct 169 ms 81000 KB Output is correct
89 Correct 274 ms 87252 KB Output is correct
90 Correct 249 ms 87508 KB Output is correct
91 Correct 196 ms 86460 KB Output is correct
92 Correct 175 ms 85992 KB Output is correct
93 Correct 66 ms 77228 KB Output is correct
94 Correct 59 ms 77220 KB Output is correct
95 Correct 254 ms 78960 KB Output is correct
96 Correct 210 ms 78816 KB Output is correct
97 Correct 297 ms 85964 KB Output is correct
98 Correct 297 ms 85912 KB Output is correct
99 Correct 192 ms 84252 KB Output is correct
100 Correct 203 ms 84368 KB Output is correct
101 Correct 75 ms 77012 KB Output is correct
102 Correct 75 ms 77060 KB Output is correct
103 Correct 206 ms 93128 KB Output is correct
104 Correct 200 ms 93116 KB Output is correct
105 Runtime error 433 ms 413272 KB Execution killed with signal 11
106 Halted 0 ms 0 KB -