oj.uz

Submission #881008

# Submission time Handle Problem Language Result Execution time Memory
881008 2023-11-30T10:42:38 Z epicci23 Vinjete (COI22_vinjete) C++17
69 / 100
 784 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define pb push_back
#define endl '\n'
#define all(x) ((x).begin(),(x).end())
#define sz(x) ((int)(x).size())

const int N = 1e5 + 5;

struct Node{
  Node* lc;Node* rc;
  int lf,rg;
  int mini,cnt,lazy;
  Node(int ll,int rr){
    lc=rc=NULL;
    lazy=mini=0;
    lf=ll; rg=rr;
    cnt=rr-ll+1;
  }
};

Node* root;

void push(Node *rt){
  if(rt==NULL) return;
  int hl = rt->lf,hr = rt->rg;
  int hm = (hl+hr)/2;
  int u = rt->lazy;
  rt->mini+=u; rt->lazy=0;

  if(rt->lc==NULL)rt->lc=new Node(hl,hm);
  rt->lc->lazy+=u;
  
  if(rt->rc==NULL) rt->rc=new Node(hm+1,hr);
  rt->rc->lazy+=u;

  return;
}

void update(Node* rt,int l,int r,int gl,int gr,int u){
  push(rt);
  if(rt==NULL) return;
  if(r<gl || l>gr) return;
  if(l>=gl && r<=gr){
    rt->lazy+=u;
    push(rt); 
    return;
  }
  int mi = (l+r)/2;
  update(rt->lc,l,mi,gl,gr,u);
  update(rt->rc,mi+1,r,gl,gr,u);
  rt->mini=min(rt->lc->mini,rt->rc->mini);
  rt->cnt=0;
  if(rt->mini==rt->lc->mini) rt->cnt+=rt->lc->cnt;
  if(rt->mini==rt->rc->mini) rt->cnt+=rt->rc->cnt;
}

vector<array<int,3>> v[N];
int ans[N],n,m;

void dfs(int c,int p){
  push(root);

  if(root->mini==0) ans[c] = m - root->cnt;
  else ans[c]=m;

  for(auto x:v[c]){
    if(x[0]==p) continue;
    update(root,1,m,x[1],x[2],1);
    dfs(x[0],c);
    update(root,1,m,x[1],x[2],-1);
  }
}

void solve(){
  
  cin >> n >> m;
  root=new Node(1,m);
  for(int i=1;i<n;i++){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    v[a].pb({b,c,d});
    v[b].pb({a,c,d});
  }
  
  dfs(1,0);

  for(int i=2;i<=n;i++) cout << ans[i] << endl;
}

int32_t main(){
  ios::sync_with_stdio(0);cin.tie(0);
  int t=1;//cin >> t;
  while(t--) solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3428 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3684 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 1 ms 3412 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 3 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3676 KB Output is correct
13 Correct 2 ms 3688 KB Output is correct
14 Correct 2 ms 3676 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 2 ms 3668 KB Output is correct
19 Correct 2 ms 3676 KB Output is correct
20 Correct 2 ms 3676 KB Output is correct
21 Correct 2 ms 3552 KB Output is correct
22 Correct 2 ms 3672 KB Output is correct
23 Correct 1 ms 3420 KB Output is correct
24 Correct 1 ms 3420 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3428 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3684 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 1 ms 3412 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 3 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3676 KB Output is correct
13 Correct 2 ms 3688 KB Output is correct
14 Correct 2 ms 3676 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 2 ms 3668 KB Output is correct
19 Correct 2 ms 3676 KB Output is correct
20 Correct 2 ms 3676 KB Output is correct
21 Correct 2 ms 3552 KB Output is correct
22 Correct 2 ms 3672 KB Output is correct
23 Correct 1 ms 3420 KB Output is correct
24 Correct 1 ms 3420 KB Output is correct
25 Correct 3 ms 3420 KB Output is correct
26 Correct 5 ms 3592 KB Output is correct
27 Correct 11 ms 12356 KB Output is correct
28 Correct 9 ms 12376 KB Output is correct
29 Correct 6 ms 8612 KB Output is correct
30 Correct 6 ms 8540 KB Output is correct
31 Correct 9 ms 12380 KB Output is correct
32 Correct 10 ms 12380 KB Output is correct
33 Correct 9 ms 12636 KB Output is correct
34 Correct 9 ms 12640 KB Output is correct
35 Correct 6 ms 3616 KB Output is correct
36 Correct 6 ms 3576 KB Output is correct
37 Correct 11 ms 12376 KB Output is correct
38 Correct 11 ms 12380 KB Output is correct
39 Correct 6 ms 8440 KB Output is correct
40 Correct 6 ms 8540 KB Output is correct
41 Correct 9 ms 12380 KB Output is correct
42 Correct 9 ms 12380 KB Output is correct
43 Correct 4 ms 3420 KB Output is correct
44 Correct 3 ms 3420 KB Output is correct
45 Correct 10 ms 12392 KB Output is correct
46 Correct 10 ms 12380 KB Output is correct
47 Correct 6 ms 8284 KB Output is correct
48 Correct 6 ms 8284 KB Output is correct
49 Correct 9 ms 12380 KB Output is correct
50 Correct 11 ms 12380 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3428 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3684 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 1 ms 3412 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 3 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3676 KB Output is correct
13 Correct 2 ms 3688 KB Output is correct
14 Correct 2 ms 3676 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 2 ms 3668 KB Output is correct
19 Correct 2 ms 3676 KB Output is correct
20 Correct 2 ms 3676 KB Output is correct
21 Correct 2 ms 3552 KB Output is correct
22 Correct 2 ms 3672 KB Output is correct
23 Correct 1 ms 3420 KB Output is correct
24 Correct 1 ms 3420 KB Output is correct
25 Correct 58 ms 10052 KB Output is correct
26 Correct 60 ms 10064 KB Output is correct
27 Correct 78 ms 19280 KB Output is correct
28 Correct 76 ms 19280 KB Output is correct
29 Correct 53 ms 19520 KB Output is correct
30 Correct 54 ms 19444 KB Output is correct
31 Correct 9 ms 9052 KB Output is correct
32 Correct 9 ms 9048 KB Output is correct
33 Correct 10 ms 9052 KB Output is correct
34 Correct 10 ms 9040 KB Output is correct
35 Correct 58 ms 7556 KB Output is correct
36 Correct 58 ms 7504 KB Output is correct
37 Correct 101 ms 16724 KB Output is correct
38 Correct 86 ms 16928 KB Output is correct
39 Correct 56 ms 16884 KB Output is correct
40 Correct 51 ms 16732 KB Output is correct
41 Correct 9 ms 8796 KB Output is correct
42 Correct 11 ms 8732 KB Output is correct
43 Correct 58 ms 7032 KB Output is correct
44 Correct 60 ms 7044 KB Output is correct
45 Correct 95 ms 16508 KB Output is correct
46 Correct 77 ms 16388 KB Output is correct
47 Correct 53 ms 16720 KB Output is correct
48 Correct 52 ms 16360 KB Output is correct
49 Correct 10 ms 8796 KB Output is correct
50 Correct 10 ms 8796 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3428 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3684 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 1 ms 3412 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 3 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3676 KB Output is correct
13 Correct 2 ms 3688 KB Output is correct
14 Correct 2 ms 3676 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 2 ms 3668 KB Output is correct
19 Correct 2 ms 3676 KB Output is correct
20 Correct 2 ms 3676 KB Output is correct
21 Correct 2 ms 3552 KB Output is correct
22 Correct 2 ms 3672 KB Output is correct
23 Correct 1 ms 3420 KB Output is correct
24 Correct 1 ms 3420 KB Output is correct
25 Correct 58 ms 10052 KB Output is correct
26 Correct 60 ms 10064 KB Output is correct
27 Correct 78 ms 19280 KB Output is correct
28 Correct 76 ms 19280 KB Output is correct
29 Correct 53 ms 19520 KB Output is correct
30 Correct 54 ms 19444 KB Output is correct
31 Correct 9 ms 9052 KB Output is correct
32 Correct 9 ms 9048 KB Output is correct
33 Correct 10 ms 9052 KB Output is correct
34 Correct 10 ms 9040 KB Output is correct
35 Correct 58 ms 7556 KB Output is correct
36 Correct 58 ms 7504 KB Output is correct
37 Correct 101 ms 16724 KB Output is correct
38 Correct 86 ms 16928 KB Output is correct
39 Correct 56 ms 16884 KB Output is correct
40 Correct 51 ms 16732 KB Output is correct
41 Correct 9 ms 8796 KB Output is correct
42 Correct 11 ms 8732 KB Output is correct
43 Correct 58 ms 7032 KB Output is correct
44 Correct 60 ms 7044 KB Output is correct
45 Correct 95 ms 16508 KB Output is correct
46 Correct 77 ms 16388 KB Output is correct
47 Correct 53 ms 16720 KB Output is correct
48 Correct 52 ms 16360 KB Output is correct
49 Correct 10 ms 8796 KB Output is correct
50 Correct 10 ms 8796 KB Output is correct
51 Correct 149 ms 20308 KB Output is correct
52 Correct 155 ms 20304 KB Output is correct
53 Correct 263 ms 43580 KB Output is correct
54 Correct 263 ms 43564 KB Output is correct
55 Correct 172 ms 43932 KB Output is correct
56 Correct 178 ms 44112 KB Output is correct
57 Correct 33 ms 22312 KB Output is correct
58 Correct 33 ms 22380 KB Output is correct
59 Correct 34 ms 22364 KB Output is correct
60 Correct 33 ms 22364 KB Output is correct
61 Correct 164 ms 13632 KB Output is correct
62 Correct 152 ms 13904 KB Output is correct
63 Correct 251 ms 36688 KB Output is correct
64 Correct 237 ms 37200 KB Output is correct
65 Correct 164 ms 37332 KB Output is correct
66 Correct 164 ms 37004 KB Output is correct
67 Correct 40 ms 20908 KB Output is correct
68 Correct 32 ms 20816 KB Output is correct
69 Correct 166 ms 12628 KB Output is correct
70 Correct 164 ms 12704 KB Output is correct
71 Correct 273 ms 35896 KB Output is correct
72 Correct 244 ms 35896 KB Output is correct
73 Correct 177 ms 36176 KB Output is correct
74 Correct 170 ms 36236 KB Output is correct
75 Correct 39 ms 20760 KB Output is correct
76 Correct 36 ms 20820 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3428 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3684 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 1 ms 3412 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 3 ms 3416 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3676 KB Output is correct
13 Correct 2 ms 3688 KB Output is correct
14 Correct 2 ms 3676 KB Output is correct
15 Correct 1 ms 3420 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 2 ms 3668 KB Output is correct
19 Correct 2 ms 3676 KB Output is correct
20 Correct 2 ms 3676 KB Output is correct
21 Correct 2 ms 3552 KB Output is correct
22 Correct 2 ms 3672 KB Output is correct
23 Correct 1 ms 3420 KB Output is correct
24 Correct 1 ms 3420 KB Output is correct
25 Correct 3 ms 3420 KB Output is correct
26 Correct 5 ms 3592 KB Output is correct
27 Correct 11 ms 12356 KB Output is correct
28 Correct 9 ms 12376 KB Output is correct
29 Correct 6 ms 8612 KB Output is correct
30 Correct 6 ms 8540 KB Output is correct
31 Correct 9 ms 12380 KB Output is correct
32 Correct 10 ms 12380 KB Output is correct
33 Correct 9 ms 12636 KB Output is correct
34 Correct 9 ms 12640 KB Output is correct
35 Correct 6 ms 3616 KB Output is correct
36 Correct 6 ms 3576 KB Output is correct
37 Correct 11 ms 12376 KB Output is correct
38 Correct 11 ms 12380 KB Output is correct
39 Correct 6 ms 8440 KB Output is correct
40 Correct 6 ms 8540 KB Output is correct
41 Correct 9 ms 12380 KB Output is correct
42 Correct 9 ms 12380 KB Output is correct
43 Correct 4 ms 3420 KB Output is correct
44 Correct 3 ms 3420 KB Output is correct
45 Correct 10 ms 12392 KB Output is correct
46 Correct 10 ms 12380 KB Output is correct
47 Correct 6 ms 8284 KB Output is correct
48 Correct 6 ms 8284 KB Output is correct
49 Correct 9 ms 12380 KB Output is correct
50 Correct 11 ms 12380 KB Output is correct
51 Correct 58 ms 10052 KB Output is correct
52 Correct 60 ms 10064 KB Output is correct
53 Correct 78 ms 19280 KB Output is correct
54 Correct 76 ms 19280 KB Output is correct
55 Correct 53 ms 19520 KB Output is correct
56 Correct 54 ms 19444 KB Output is correct
57 Correct 9 ms 9052 KB Output is correct
58 Correct 9 ms 9048 KB Output is correct
59 Correct 10 ms 9052 KB Output is correct
60 Correct 10 ms 9040 KB Output is correct
61 Correct 58 ms 7556 KB Output is correct
62 Correct 58 ms 7504 KB Output is correct
63 Correct 101 ms 16724 KB Output is correct
64 Correct 86 ms 16928 KB Output is correct
65 Correct 56 ms 16884 KB Output is correct
66 Correct 51 ms 16732 KB Output is correct
67 Correct 9 ms 8796 KB Output is correct
68 Correct 11 ms 8732 KB Output is correct
69 Correct 58 ms 7032 KB Output is correct
70 Correct 60 ms 7044 KB Output is correct
71 Correct 95 ms 16508 KB Output is correct
72 Correct 77 ms 16388 KB Output is correct
73 Correct 53 ms 16720 KB Output is correct
74 Correct 52 ms 16360 KB Output is correct
75 Correct 10 ms 8796 KB Output is correct
76 Correct 10 ms 8796 KB Output is correct
77 Correct 149 ms 20308 KB Output is correct
78 Correct 155 ms 20304 KB Output is correct
79 Correct 263 ms 43580 KB Output is correct
80 Correct 263 ms 43564 KB Output is correct
81 Correct 172 ms 43932 KB Output is correct
82 Correct 178 ms 44112 KB Output is correct
83 Correct 33 ms 22312 KB Output is correct
84 Correct 33 ms 22380 KB Output is correct
85 Correct 34 ms 22364 KB Output is correct
86 Correct 33 ms 22364 KB Output is correct
87 Correct 164 ms 13632 KB Output is correct
88 Correct 152 ms 13904 KB Output is correct
89 Correct 251 ms 36688 KB Output is correct
90 Correct 237 ms 37200 KB Output is correct
91 Correct 164 ms 37332 KB Output is correct
92 Correct 164 ms 37004 KB Output is correct
93 Correct 40 ms 20908 KB Output is correct
94 Correct 32 ms 20816 KB Output is correct
95 Correct 166 ms 12628 KB Output is correct
96 Correct 164 ms 12704 KB Output is correct
97 Correct 273 ms 35896 KB Output is correct
98 Correct 244 ms 35896 KB Output is correct
99 Correct 177 ms 36176 KB Output is correct
100 Correct 170 ms 36236 KB Output is correct
101 Correct 39 ms 20760 KB Output is correct
102 Correct 36 ms 20820 KB Output is correct
103 Correct 250 ms 21264 KB Output is correct
104 Correct 246 ms 21228 KB Output is correct
105 Runtime error 784 ms 524288 KB Execution killed with signal 9
106 Halted 0 ms 0 KB -