International Odoo Programming Contest 2024 Editorial

Revision en4, by Mtaylor, 2024-03-27 11:11:06

This is the editorial for the first edition of the International Odoo Programming Contest

Author: pauloamed

105056A - Potential Odoo Email

Editorial
Solution

Author: pauloamed

105056B - Make it ODOO!

Editorial
Solution

Author: ghrissiraouf

105056C - Viruses

Editorial
Solution

Author: NatanSG

105056D - Tasks at Odoo

Editorial
Solution

Author: Mtaylor

105056E - POS Kiosk

Editorial

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
typedef long long ll;
const int N = 3e5 + 5;

int t;
int n;
ll a[N];
ll sum[N];
vector<int> p;
void test_case() {
    cin >> n;
    p.clear();
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll s = 0;
    sum[n] = 0;
    p.pb(n);
    ll cur = 0;
    ll ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        s += a[i];
        sum[i] = s;
        while (p.size() && sum[p.back()] > s) {
            int y = p.back();
            p.pop_back();
            int x = -1;
            if (p.size()) {
                x = p.back();
            }
            if (x != -1) {
                cur -= sum[y] * (x - y);
            } else {
                cur -= sum[y] * (n + 1 - y);
            }
        }
        int x = -1;
        if (p.size()) {
            x = p.back();
        }
        if (x != -1) {
            cur += sum[i] * (x - i);
        } else {
            cur += sum[i] * (n + 1 - i);
        }
        p.push_back(i);
        ans -= cur;
        ans += sum[i] * (n - i + 1);
    }
    cout << ans << endl;
}

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}

Author maghrabyJr_

105056F - Odoo Trees

Editorial

Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long
int n, k, q;
struct segmentTree{
        vector<int> values;
        int sz = 1;
        void init(int n){
                while(sz < n) sz *= 2;
                values.resize(2 * sz, 1);
        }
        void set(int i, int v, int x, int lx, int rx){
                if(rx - lx == 1){
                        values[x] = v % k;
                        return;
                }
                int m = (lx + rx) >> 1;
                if(i < m)
                        set(i, v, 2 * x + 1, lx, m);
                else
                        set(i, v, 2 * x + 2, m, rx);

                values[x] = values[2 * x + 1] * values[2 * x + 2] % k;
        }
        void set(int i, int v){
                set(i, v, 0, 0, sz);
        }

        int ans(int x, int lx, int rx, int ai){
                if (rx - lx == 1){
                        return lx;
                }
                int m = (lx + rx) >> 1;
                if (values[2 * x + 1] * ai % k == 0){
                        return ans(2 * x + 1, lx, m, ai);
                }
                return ans(2 * x + 2, m, rx, ai * values[2 * x + 1] % k);
        }
        int ans(int x){
                if (x % k == 0)
                        return 0;
                if (values[0] * x % k != 0)
                        return -1;
                return ans(0, 0, sz, x);
        }
};

const int N = 2e5 + 10;
vector<int> adj[N];
int ans[N], a[N];
vector<pair<int,int>> updates[N];
segmentTree st;

void dfs(int node, int p){
        for (auto [i, y] : updates[node]){
                st.set(i, y);
        }
        ans[node] = st.ans(a[node]);
        for(int ch : adj[node]){
                if(ch != p)
                        dfs(ch, node);
        }
        for (auto [i, y] : updates[node]){
            st.set(i, 1);
        }
}
int32_t main() {
        cin.tie(0);
        cin.sync_with_stdio(0);

        cin>>n>>k>>q;
        for(int i = 0; i < n; i++){
                cin>>a[i]; a[i] %= k;
        }
        for(int i = 1; i < n; i++){
                int p; cin>>p; --p;
                adj[p].push_back(i);
        }
        for(int i = 1; i <= q; i++){
                int x, y;
                cin>>x>>y;
                updates[x - 1].push_back({i, y});
        }
        st.init(q + 10);
        dfs(0, 0);
        for(int i = 0; i < n; i++){
                cout<<ans[i]<<' ';
        }
}

Author: kinhosz

105056G - Giant Community

Editorial

Solution

v_pr = []
v_bonus = []
adj = []
query = []
offline = []
ans = []
added = []
parent = []

class Line:
  def __init__(self, m, c):
    self.m = m
    self.c = c


class CHTPersistent:
  def __init__(self):
    self.hull = []
    self.SZ = 0
    self.version_idx = []
    self.version_sz = []

  def inter(self, t1, t2):
    ret = (t2.c - t1.c)/(t1.m - t2.m)
    return ret

  def add2(self, curr):
    self.version_sz.append(self.SZ)

    if self.SZ > 1:
      s = 0
      e = self.SZ-1

      while s < e:
        p = (s+e)//2

        temp = self.hull[p+1][-1]
        temp2 = self.hull[p][-1]

        point = self.inter(temp, temp2)
        point2 = self.inter(temp, curr)

        if point < point2:
          s = p+1
        else:
          e = p

      self.SZ = s+1
    

    if len(self.hull) == self.SZ:
      x = []
      self.hull.append(x)

    self.hull[self.SZ].append(curr)
    self.version_idx.append(self.SZ)
    self.SZ+=1

  def add(self, m, c):
    self.add2(Line(m, c))

  def query(self, find):
    s = 0
    e = self.SZ-1

    while s < e:
      p = (s+e)//2

      point = self.inter(self.hull[p][-1], self.hull[p+1][-1])
      if point < find:
        s = p+1
      else:
        e = p

    ret = (self.hull[s][-1].m * find) + self.hull[s][-1].c
    return ret
  

  def rollback(self):
    self.SZ = self.version_sz[-1]
    self.version_sz.pop()
    self.hull[self.version_idx[-1]].pop()
    self.version_idx.pop()

  def size(self):
    return self.SZ

cht = CHTPersistent()

def dfs(u):
  while u != -1:
    if added[u] == False:
      cht.add(v_pr[u], v_bonus[u])

      for q_id in offline[u]:
        d = query[q_id]
        ans[q_id] = cht.query(d)

      added[u] = True

    if len(adj[u]) > 0:
      v = adj[u][-1]
      adj[u].pop()
      u = v
    else:
      cht.rollback()
      u = parent[u]

def main():
  txt = input().split()
  n = int(txt[0])
  q = int(txt[1])

  for i in range(n):
    adj.append([])
    v_pr.append(0)
    v_bonus.append(0)
    offline.append([])
    added.append(False)
    parent.append(0)

  for i in range(q):
    ans.append(0)

  root = -1

  for i in range(n):
    txt = input().split()

    idd = int(txt[0])
    pid = int(txt[1])
    pr = int(txt[2])
    bonus = int(txt[3])

    idd -= 1
    pid -= 1
    v_pr[idd] = pr
    v_bonus[idd] = bonus
    if pid == -1:
      root = idd
    else :
      adj[pid].append(idd)

    parent[idd] = pid

  for i in range(q):
    txt = input().split()
    idd = int(txt[0])
    d = int(txt[1])

    idd -= 1
    query.append(d)
    offline[idd].append(i)

  dfs(root)

  for i in range(q):
    print(ans[i])
	
if __name__ == "__main__":
  main()

Author: Mtaylor

105056H - Views Testing

Editorial

Solution

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
typedef long long ll;
const int N = 1e5 + 5;
const int E = 1e6 + 5;

#define neig(u, v, e, g) \
    for (int e = g.head[u], v; ~e && ((v = g.to[e]), 1); e = g.nxt[e])

class ADJ {
   public:
    int head[E], to[E], nxt[E], n, edgcnt = 0;
    ll cst[E];

    void addEdge(int a, int b, int c = 0) {
        nxt[edgcnt] = head[a];
        head[a] = edgcnt;
        to[edgcnt] = b;
        cst[edgcnt] = c;
        edgcnt++;
    }

    void addBiEdge(int a, int b, int c = 0) {
        addEdge(a, b, c);
        addEdge(b, a, c);
    }
    void init(int _n) {
        n = _n;
        memset(head, -1, n * sizeof(head[0]));
        edgcnt = 0;
    }
} adj;

set<int> tree[4 * N];
int n, k, q;
int v[N];
int t, p, u;
set<int>::iterator it;
int getVal(int id, int k) {
    if (!tree[id].size()) return -1;

    it = tree[id].lower_bound(k);
    if (it != tree[id].end()) {
        return *it;
    }
    return *tree[id].begin();
}

int mrg(int x, int y, int k) {
    if (x == -1 || y == -1) return max(x, y);
    if (x >= k && y >= k) {
        return min(x, y);
    }
    if (x < k && y < k) {
        return min(x, y);
    }
    return max(x, y);
}

int queryPosition(int qp, int k, int id = 0, int ns = 0, int ne = n - 1) {
    int rs = getVal(id, k);
    if (ns == ne) {
        return rs;
    }
    int l = 2 * id + 1;
    int r = l + 1;
    int md = ns + (ne - ns) / 2;
    if (qp <= md) {
        rs = mrg(rs, queryPosition(qp, k, l, ns, md), k);
    } else {
        rs = mrg(rs, queryPosition(qp, k, r, md + 1, ne), k);
    }
    return rs;
}

void updateRange(int qs, int qe, int p, int to_ins, int id = 0, int ns = 0,
                 int ne = n - 1) {
    if (qs > ne || qe < ns) return;
    if (qs <= ns && qe >= ne) {
        if (to_ins) {
            tree[id].insert(p);
        } else {
            tree[id].erase(p);
        }
        return;
    }
    int l = 2 * id + 1;
    int r = l + 1;
    int md = ns + (ne - ns) / 2;
    updateRange(qs, qe, p, to_ins, l, ns, md);
    updateRange(qs, qe, p, to_ins, r, md + 1, ne);
}

class HLD {
   public:
    vector<int> par, sze, dpth, ndToIdx, chHead, heavyChld, idxToNd;
    int n, curPos;
    HLD() {}
    void run(ADJ &adj) {
        n = adj.n;
        curPos = 0;
        par.assign(n, -1);
        sze.assign(n, 0);
        dpth.assign(n, 0);
        ndToIdx.assign(n, 0);
        chHead.assign(n, 0);
        heavyChld.assign(n, 0);
        idxToNd.assign(n, 0);
        calcsz(0, adj);
        HLD_util(0, adj);
    }

    void calcsz(int u, ADJ &adj) {
        heavyChld[u] = -1;
        sze[u] = 1;
        int mx = 0, mxv;
        neig(u, v, e, adj) {
            if (par[u] == v) continue;
            par[v] = u;
            dpth[v] = dpth[u] + 1;
            calcsz(v, adj);
            if (sze[v] > mx) {
                mx = sze[v];
                mxv = v;
            }
            sze[u] += sze[v];
        }
        if (mx * 2 > sze[u]) {
            heavyChld[u] = mxv;
        }
    }

    void HLD_util(int u, ADJ &adj, int c = 0) {
        if (u == -1) return;
        idxToNd[curPos] = u;
        ndToIdx[u] = curPos++;
        chHead[u] = c;
        HLD_util(heavyChld[u], adj, c);
        neig(u, v, e, adj) {
            if (v == par[u]) continue;
            if (v == heavyChld[u]) continue;
            HLD_util(v, adj, v);
        }
    }
    int lca(int u, int v) {
        while (chHead[u] != chHead[v]) {
            if (dpth[chHead[v]] > dpth[chHead[u]]) swap(u, v);
            u = par[chHead[u]];
        }
        if (dpth[u] > dpth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) { return dpth[u] + dpth[v] - 2 * dpth[lca(u, v)]; }
    // make sure to update the return type based on the type of the segment
    // tree
    int query(int u, int k) { return queryPosition(ndToIdx[u], k); }

    void update(int u, int v, int p, int to_insert) {
        while (chHead[u] != chHead[v]) {
            if (dpth[chHead[v]] > dpth[chHead[u]]) {
                swap(u, v);
            }
            updateRange(ndToIdx[chHead[u]], ndToIdx[u], p, to_insert);
            u = par[chHead[u]];
        }
        if (dpth[u] > dpth[v]) {
            swap(u, v);
        }
        updateRange(ndToIdx[u], ndToIdx[v], p, to_insert);
    }
} hld;
template <typename T>
class FenwickTree {
   public:
    vector<T> tree;
    int n;
    void init(int n) {
        tree.assign(n + 2, 0);
        this->n = n;
    }
    T mrg(T &x, T &y) { return x + y; }

    void upd(int x, T v) {
        for (; x <= n; x += (x) & (-x)) {
            tree[x] = mrg(tree[x], v);
        }
    }
    T getprefix(int x) {
        if (x <= 0) return 0;
        T rs = 0;
        for (; x; x -= (x) & (-x)) {
            rs = mrg(rs, tree[x]);
        }
        return rs;
    }
    T getrange(int l, int r) { return getprefix(r) - getprefix(l - 1); }
};
FenwickTree<ll> ft;

void solve_1() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        p--;
        u--;
        if (t == 1) {
            v[p] = u;
        } else {
            if (v[0] == u) {
                cout << 0 << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
}

void solve_2() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        p--;
        u--;
        if (t == 1) {
            v[p] = u;
        } else {
            if (hld.dist(v[0], u) + hld.dist(v[1], u) == hld.dist(v[0], v[1])) {
                cout << hld.dist(v[p], u) << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
}

void solve() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        --u, --p;
        if (t == 1) {
            int d = hld.dist(v[p], v[(p + 1) % k]);
            ft.upd(p + 1, -d);
            hld.update(v[p], v[(p + 1) % k], p, 0);

            int b = (p + k - 1) % k;
            d = hld.dist(v[p], v[b]);
            hld.update(v[b], v[p], b, 0);
            ft.upd(b+1, -d);
            v[p] = u;
            d = hld.dist(v[p], v[(p + 1) % k]);
            ft.upd(p + 1, d);
            hld.update(v[p], v[(p + 1) % k], p, 1);
            d = hld.dist(v[p], v[b]);
            ft.upd(b+1, d);
            hld.update(v[b], v[p], b, 1);
        } else {
            int pos = hld.query(u, p);
            if (pos == -1) {
                cout << -1 << endl;
                continue;
            }
            ll dist = hld.dist(v[pos], u);

            if (pos >= p) {
                dist += ft.getrange(p + 1, pos);
            } else {
                dist += ft.getrange(p + 1, k);
                dist += ft.getprefix(pos);
            }
            cout << dist << endl;
        }
    }
}

void test_case() {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        cin >> v[i];
        --v[i];
    }
    adj.init(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj.addBiEdge(u, v);
    }
    ft.init(k + 1);
    hld.run(adj);
    for (int i = 0; i < k; i++) {
        hld.update(v[i], v[(i + 1) % k], i, 1);
        ft.upd(i + 1, hld.dist(v[i], v[(i + 1) % k]));
    }
    cin >> q;
    if (k == 1) {
        solve_1();
    } else if (k == 2) {
        solve_2();
    } else {
        solve();
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--) {
        test_case();
    }
    return 0;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English Mtaylor 2024-03-29 14:13:27 3 Tiny change: ' of node ${u}, the answ' -> ' of node $$u$, the answ'
en17 English Mtaylor 2024-03-29 14:02:20 37
en16 English Mtaylor 2024-03-29 13:57:27 0 (published)
en15 English Mtaylor 2024-03-29 13:57:17 698
en14 English Mtaylor 2024-03-28 17:28:16 18
en13 English Mtaylor 2024-03-28 17:26:44 50
en12 English Mtaylor 2024-03-28 17:25:12 1492
en11 English Mtaylor 2024-03-28 12:20:35 10513
en10 English Mtaylor 2024-03-28 11:58:28 682
en9 English Mtaylor 2024-03-28 11:56:00 593
en8 English Mtaylor 2024-03-28 11:24:39 450
en7 English Mtaylor 2024-03-27 14:30:34 2713
en6 English Mtaylor 2024-03-27 11:25:39 14
en5 English Mtaylor 2024-03-27 11:23:58 907
en4 English Mtaylor 2024-03-27 11:11:06 1304
en3 English Mtaylor 2024-03-27 10:44:25 288 Tiny change: 'lem:105056]\n\n<spoi' -> 'lem:105056A]\n\n<spoi'
en2 English Mtaylor 2024-03-27 10:40:43 34
en1 English Mtaylor 2024-03-27 10:39:38 22709 Initial revision (saved to drafts)