Submission #701374

#	Time	Username	Problem	Language	Result	Execution time	Memory
701374		Nursik	Colors (RMI18_colors)	C++14	52 / 100	3059 ms	46312 KiB

colors

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 2e5 + 1, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blck = 400, p2 = 31;
const ld eps = 1e-9;
 
int t;
int n, m, ver;
int a[maxn], b[maxn], pos[maxn], blocked[maxn], par[maxn];
int used[maxn];
set<int> setik[maxn];
vector<int> g[maxn], pth;
struct seg_tree{
    int t[maxn * 4], t2[maxn * 4], mv[maxn * 4];
    void push(int v, int l, int r){
        if (mv[v] != inf){
            t[v] = min(t[v], mv[v]);
            if (l != r){
                mv[v + v] = min(mv[v + v], mv[v]);
                mv[v + v + 1] = min(mv[v + v + 1], mv[v]);
            }
            mv[v] = inf;
        }
    }
    void upd(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
        if (tl == tr){
            t[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm){
            upd(pos, val, v + v, tl, tm);
        }
        else{
            upd(pos, val, v + v + 1, tm + 1, tr);
        }
        t[v] = min(t[v + v], t[v + v + 1]);
    }
    void updlr(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
        push(v, tl, tr);
        if (l <= tl && tr <= r){
            mv[v] = min(mv[v], val);
            push(v, tl, tr);
            return;
        }
        if (l > tr || r < tl)
            return;
        int tm = (tl + tr) / 2;
        updlr(l, r, val, v + v, tl, tm);
        updlr(l, r, val, v + v + 1, tm + 1, tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
    void upd2(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
        if (tl == tr){
            t2[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm){
            upd2(pos, val, v + v, tl, tm);
        }
        else{
            upd2(pos, val, v + v + 1, tm + 1, tr);
        }
        t2[v] = max(t2[v + v], t2[v + v + 1]);
    }
    int getn(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
        push(v, tl, tr);
        if (l <= tl && tr <= r){
            return t[v];
        }
        if (l > tr || r < tl)
            return inf;
        int tm = (tl + tr) / 2;
        return min(getn(l, r, v + v, tl, tm), getn(l, r, v + v + 1, tm + 1, tr));
    }
    int getx(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
        if (l <= tl && tr <= r){
            return t2[v];
        }
        if (l > tr || r < tl)
            return -inf;
        int tm = (tl + tr) / 2;
        return max(getx(l, r, v + v, tl, tm), getx(l, r, v + v + 1, tm + 1, tr));
    }
} rt;
void dfs(int v, int p){
    pth.pb(v);
    for (auto to : g[v]){
        if (to != p){
            dfs(to, v);
        }
    }
}
void dfs(int v, int p, int x){
    if (a[v] == x){
        ver = v;
        return;
    }
    for (auto to : g[v]){
        if (to != p){
        if (blocked[to] == 0 && a[to] >= x){
            par[to] = v;
            dfs(to, v, x);
        }
        else if (blocked[to] == 1 && a[to] == x){
            par[to] = v;
            dfs(to, v, x);
        }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> m;
        for (int i = 1; i <= n * 4; ++i){
            rt.t[i] = inf;
            rt.t2[i] = 0;
            rt.mv[i] = inf;
        }
        pth.clear();
        for (int i = 1; i <= n; ++i){
            cin >> a[i];
            used[a[i]] = 1;
            setik[a[i]].insert(i);
        }
        for (int i = 1; i <= n; ++i){
            cin >> b[i];
        }
        for (int i = 1; i <= m; ++i){
            int u, v;
            cin >> u >> v;
            g[u].pb(v);
            g[v].pb(u);
        }
        int chain = (n - 1 == m);
        for (int i = 1; i <= n; ++i){
            chain &= ((int)g[i].size() <= 2);
        }
        if (chain){
            int st = -1;
            for (int i = 1; i <= n; ++i){
                if ((int)g[i].size() <= 1){
                    st = i;
                    break;
                }
            }
            dfs(st, 0);
            for (int i = 0; i < n; ++i){
                rt.upd(i, a[pth[i]]);
                pos[pth[i]] = i;
            }
            vector<pair<int, int>> vec;
            for (int i = 1; i <= n; ++i){
                vec.pb(mp(b[i], i));
            }
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
            int bad = 0;
          /*  for (auto it : pth){
                cout << it << " ";
            }
           / cout << '\n';
            for (auto it : pth){
                cout << a[it] << " ";
            }
            cout << '\n';
            cout << "start\n";*/
            for (int i = 0; i < n; ++i){
                pair<int, int> cur = vec[i];
                int x = pos[cur.s];
               // cout << cur.f << " " << x << " " << cur.s << '\n';
                if (cur.f == rt.getn(x, x)){
                    rt.upd2(x, cur.f);
                    continue;
                }
               // cout << "kek\n";
                int l = 0, r = x, ans = -1;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (rt.getn(mid, x) >= cur.f){
                        if (rt.getx(mid, x) > cur.f){
                            l = mid + 1;
                            continue;
                        }
                        r = mid - 1, ans = mid;
                    }
                    else{
                        l = mid + 1;
                    }
                }
               /* cout << ans << '\n';
                cout << rt.getn(x - 1, x) << " " << rt.getx(x - 1, x) << '\n';
                exit(0);*/
                if (rt.getn(ans, x) == cur.f && rt.getx(ans, x) <= cur.f){
                    rt.updlr(ans, x, cur.f);
                    rt.upd2(x, cur.f);
                  //  cout << ans << " " << x << " " << cur.f << '\n';
                    continue;
                }
                l = x, r = n - 1, ans = -1;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (rt.getn(x, mid) >= cur.f){
                        if (rt.getx(x, mid) > cur.f){
                            r = mid - 1;
                            continue;
                        }
                        l = mid + 1, ans = mid;
                    }
                    else{
                        r = mid - 1;
                    }
                }
                if (rt.getn(x, ans) == cur.f && rt.getx(ans, x) <= cur.f){
                    rt.updlr(x, ans, cur.f);
                    rt.upd2(x, cur.f);
                    continue;
                }
                bad = 1;
                break;
            }
           // cout << "end\n";
            for (int i = 0; i < n; ++i){
                int x = rt.getn(i, i);
               // cout << x << " " << b[pth[i]] << '\n';
                if (x != b[pth[i]]){
                    bad = 1;
                    break;
                }
            }
            if (bad){
                cout << 0 << '\n';
            }
            else{
                cout << 1 << '\n';
            }
            for (int i = 1; i <= n; ++i){
                used[i] = 0;
                setik[i].clear();
                g[i].clear();
            }
            continue;
        }
        int star = 0;
        int complt = (n * (n - 1) / 2 == m);
        if (complt){
            vector<pair<int, int>> vec;
            for (int i = 1; i <= n; ++i){
                vec.pb(mp(b[i], i));
            }
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
            int bad = 0;
            for (int i = 0; i < n; ++i){
                int x = vec[i].f, y = vec[i].s;
                int ok = 0;
                for (int j = 1; j <= n; ++j){
                    if (a[j] == x){
                        ok = 1;
                        a[y] = min(a[y], a[j]);
                        break;
                    }
                }
                bad |= !ok;
            }
            for (int i = 1; i <= n; ++i){
                if (a[i] != b[i]){
                    bad = 1;
                }
            }
            if (bad){
                cout << 0 << '\n';
            }
            else{
                cout << 1 << '\n';
            }
            for (int i = 1; i <= n; ++i){
                setik[i].clear();
                used[i] = 0;
                g[i].clear();
            }
            continue;
        }
        for (int i = 1; i <= n; ++i){
            if ((int)g[i].size() == n - 1){
                star = i;
            }
        }
        if (star){
            int bad = 0;
            vector<pair<int, int>> vec;
            for (int i = 1; i <= n; ++i){
                vec.pb(mp(b[i], i));
            }
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
            for (int i = 0; i < n; ++i){
                pair<int, int> cur = vec[i];
                int x = cur.f;
                int y = cur.s;
                if (a[y] == b[y]){
                    setik[a[y]].insert(y);
                    continue;
                }
                if ((int)setik[x].size() == 0){
                    bad = 1;
                    break;
                }
                int z = *setik[x].begin();
                setik[a[star]].erase(star);
                a[star] = min(a[star], a[z]);
                setik[a[star]].insert(star);
                setik[a[y]].erase(y);
                a[y] = min(a[y], a[star]);
                setik[a[y]].insert(y);
            }
            for (int i = 1; i <= n; ++i){
                if (a[i] != b[i]){
                    bad = 1;
                }
            }
            if (bad){
                cout << 0 << '\n';
            }
            else{
                cout << 1 << '\n';
            }
        }
        else if (m == n - 1){
            vector<pair<int, int>> vec;
            for (int i = 1; i <= n; ++i){
                vec.pb(mp(b[i], i));
            }
            int bad = 0;
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
            for (int i = 0; i < n; ++i){
                pair<int, int> cur = vec[i];
                int x = cur.f, y = cur.s;
                if (a[y] == b[y]){
                    blocked[y] = 1;
                    continue;
                }
                if (a[y] < b[y]){
                    bad = 1;
                    break;
                }
                ver = -1;
                dfs(y, 0, b[y]);
                if (ver == -1){
                    bad = 1;
                    break;
                }
                vector<int> putt;
                while (ver != y){
                    putt.pb(ver);
                    ver = par[ver];
                }
                putt.pb(y);
                for (auto it : putt){
                    a[it] = min(a[it], b[y]);
                }
                blocked[y] = 1;
            }
            if (bad){
                cout << 0 << '\n';
            }
            else{
                cout << 1 << '\n';
            }
        }
        for (int i = 1; i <= n; ++i){
            used[i] = 0;
            g[i].clear();
            setik[i].clear();
            blocked[i] = 0;
        }
    }
}

Compilation message (stderr)

colors.cpp: In function 'int main()':
colors.cpp:377:21: warning: unused variable 'x' [-Wunused-variable]
  377 |                 int x = cur.f, y = cur.s;
      |                     ^

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22