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

Author: pauloamed

105056A - Potential Odoo Email

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

int main() {
    const string suffix = "@odoo.com";
    string s; cin >> s;

    int last_pos_at = s.find_last_of('@');

    if(s.size() < suffix.size()) {cout << "no\n"; return 0; }
    if(last_pos_at == string::npos) {cout << "no\n"; return 0;}
    if(last_pos_at < 2 || last_pos_at > 4) {cout << "no\n"; return 0;}
    if(s.substr(last_pos_at) != suffix) {cout << "no\n"; return 0; }
    
    for(int i = 0; i < last_pos_at; i++) {
        if(s[i] < 'a' || s[i] > 'z') {cout << "no\n"; return 0; }
    }

    cout << "yes\n";
}

Author: pauloamed

105056B - Make it ODOO!

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

int main() {
    int T; cin >> T;
    const string odoo = "ODOO";
    while(T--) {
        string s; cin >> s;

        int ans = INT_MAX;
        for(int i = 0; i + 3 < s.size(); ++i) {
            int diff = (
                (s[i] != odoo[0]) + 
                (s[i + 1] != odoo[1]) +
                (s[i + 2] != odoo[2]) +
                (s[i + 3] != odoo[3])
            );
            ans = min(ans, diff);
        }
        cout << ans + s.size() - 4 << "\n";
    }
}

Author: ghrissiraouf

105056C - Viruses

#include <bits/stdc++.h>

#define inf 1e9

struct node {
    int id;
    int p;
    int c; // c == inf to put it after the module if they have the same position

    node(int _id, int _p, int _c = inf) {
        id = _id;
        p = _p;
        c = _c;
    }
};

bool compare(node n1, node n2) {
    if (n1.p == n2.p) {
        return n1.c < n2.c;
    }

    return n1.p < n2.p;
}

using namespace std;

vector<string> solve() {
    //freopen("c.txt", "r", stdin);

    int n, m, k;

    cin>>n>>m>>k;
    vector<node> v;
    int cap[m][n];
    memset(cap, -1, sizeof cap);

    unordered_map<string, int> module_id_per_name;
    vector<string> module_name_per_id(n);
    string s;
    int c, p;
    int id = -1;
    for (int i=0 ; i<n ; i++) {
        cin>>s>>c>>p;
        module_id_per_name[s] = ++id;
        module_name_per_id[id] = s;
        v.push_back(node(id, p, c));
    }

    int num;
    for (int i=0 ; i<m ; i++) {
        cin>>num>>p;
        num--;
        v.push_back(node(num, p));
    }

    for (int i=0 ; i<k ; i++) {
        cin>>num>>s>>c;
        num--;
        cap[num][module_id_per_name[s]] = c;
    }

    sort(v.begin(), v.end(), compare);

    stack<node> st;
    stack<node> st2;

    n = v.size();
    for (int i = 0 ; i<n ; i++) {
        if (v[i].c == inf) { // virus
            int vid = v[i].id;
            while(!st.empty()) {
                node t = st.top();
                int mid = t.id;
                int vc = cap[vid][mid];
                if (vc == -1) { // can't collide
                    st2.push(t);
                    st.pop();
                } else {
                    int mc = t.c;
                    if (vc == mc) {
                        st.pop();
                        break;
                    } else if (vc < mc) {
                        st.top().c -= vc;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }

            while(!st2.empty()) {
                st.push(st2.top());
                st2.pop();
            }
        } else {
            st.push(v[i]);
        }
    }

    vector<string> ans;
    while(!st.empty()) {
        ans.push_back(module_name_per_id[st.top().id]);
        st.pop();
    }
    return ans;
}

int main() {
    auto a = solve();
    cout << a.size() << endl;
    for(auto &u:a){
        cout << u << " ";
    }
    return 0;
}

Author: NatanSG

105056D - Tasks at Odoo

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

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << "{"; for (typename vector<T>::const_iterator vi = v.begin(); vi != v.end(); ++vi) { if (vi != v.begin()) os << ", "; os << *vi; } os << "}"; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; }
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

#define optimize ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"

#define fi first 
#define se second 
#define pb push_back

#define all(x) x.begin(),x.end()
#define ms(x,a) memset(x,a,sizeof(x))

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

#define mod 1000000007LL
#define MAXN 200010

/* -------------------------------- Solution starts below -------------------------------- */

ll N, T;
ll A[MAXN];

bool check(ll m) { 
    
    priority_queue<ll, vector<ll>, greater<ll>> pq;

    for(int i = 0; i < m; i++) {
        pq.push(0);
    }

    for(int i = 0; i < N; i++) {
        ll x = pq.top();
        pq.pop();

        if(x + A[i] > T) return false;

        pq.push(x + A[i]);
    }

    return true;
}

void solve() {

    ll l = 1, r = MAXN;

    while(l < r) {
        ll m = (l + r) / 2;

        if( check(m) )  r = m;
        else            l = m + 1;
    }

    if(l == MAXN) {
        l = -1;
    }

    cout << l << endl;
}

int main() {

	optimize;
	
    cin >> N >> T;

    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

	solve();
    
	return 0;
}

Author: Mtaylor

105056E - POS Kiosk

// 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

#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

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

// 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;
}