oj.uz

Submission #675864

# Submission time Handle Problem Language Result Execution time Memory
675864 2022-12-28T08:42:34 Z Quan2003 Tree Rotations (POI11_rot) C++17
100 / 100
 208 ms 56748 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int sz =1e6+10;
const int ssz=5e3+1;
const int mod=1e9+7;
long long p,n,q,timer,m,cnt;
long long lb,rb; 
queue<int>qe;
int lf[sz],rt[sz];
int lc[sz*40],rc[sz*40];
int cap[sz*40]; 
int val[sz];
int fa[sz];
void read(int &now){
     now = ++cnt;
     scanf("%d",&val[now]);
     if(!val[now]){
         read(lf[now]);
         read(rt[now]); 
     }
}
void upd(int pos,int &num,int l = 1, int r = n){
     if(!num) num = ++timer;
     cap[num] = 1;
     if(l == r) return; 
     int mid = (l + r)>>1;
     if(pos <= mid) upd(pos,lc[num],l,mid);
     else upd(pos,rc[num],mid + 1, r);
}
int merge(int roota, int rootb){
    if(!roota or !rootb) return roota + rootb;
    cap[roota]+=cap[rootb];
    lb += (long long) cap[rc[rootb]] * cap[lc[roota]];
    rb += (long long) cap[rc[roota]] * cap[lc[rootb]]; 
    lc[roota] = merge(lc[roota],lc[rootb]);
    rc[roota] = merge(rc[roota],rc[rootb]);
    return roota;
}
long long dfs(int u){
     long long res = 0;
     if(!val[u]){
          res = dfs(lf[u]) + dfs(rt[u]);
          lb = rb = 0;
          fa[u] = merge(fa[lf[u]],fa[rt[u]]);
          res = res + min(lb,rb);
     }
     else upd(val[u],fa[u]);
     return res; 
}
int main(){
      scanf("%d",&n);
      int root;
      read(root);
      long long res = dfs(root);  
      cout<<res<<endl;
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:52:15: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   52 |       scanf("%d",&n);
      |              ~^  ~~
      |               |  |
      |               |  long long int*
      |               int*
      |              %lld
rot.cpp: In function 'void read(int&)':
rot.cpp:17:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |      scanf("%d",&val[now]);
      |      ~~~~~^~~~~~~~~~~~~~~~
rot.cpp: In function 'int main()':
rot.cpp:52:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |       scanf("%d",&n);
      |       ~~~~~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 276 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3028 KB Output is correct
2 Correct 7 ms 2900 KB Output is correct
3 Correct 21 ms 6872 KB Output is correct
4 Correct 7 ms 3284 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11864 KB Output is correct
2 Correct 28 ms 11992 KB Output is correct
3 Correct 35 ms 13864 KB Output is correct
4 Correct 32 ms 14716 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 22772 KB Output is correct
2 Correct 49 ms 22052 KB Output is correct
3 Correct 65 ms 20684 KB Output is correct
4 Correct 67 ms 21196 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 29584 KB Output is correct
2 Correct 94 ms 29612 KB Output is correct
3 Correct 73 ms 31808 KB Output is correct
4 Correct 74 ms 31400 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 44772 KB Output is correct
2 Correct 93 ms 44440 KB Output is correct
3 Correct 131 ms 43468 KB Output is correct
4 Correct 114 ms 43924 KB Output is correct
5 Correct 135 ms 42504 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 48132 KB Output is correct
2 Correct 129 ms 52044 KB Output is correct
3 Correct 161 ms 52236 KB Output is correct
4 Correct 119 ms 54096 KB Output is correct
5 Correct 151 ms 50580 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 50388 KB Output is correct
2 Correct 208 ms 53248 KB Output is correct
3 Correct 175 ms 52184 KB Output is correct
4 Correct 153 ms 52376 KB Output is correct
5 Correct 202 ms 56748 KB Output is correct
6 Correct 166 ms 52140 KB Output is correct