Codeforces Round 914 (Div. 2) Editorial

Revision en10, by oursaco, 2023-12-09 21:29:25

1904A - Forked!

Solution
Code

1904B - Collecting Game

Solution
Code

1904C - Array Game

Solution
Code

1904D1 - Set To Max (Easy Version)/1904D2 - Set To Max (Hard Version)

Hint 1
Hint 2
Solution
Code

1904E - Tree Queries

Editorial 1:

Hint 1
Hint 2
Solution
Code

Editorial 2:

Hint 1
Hint 2
Hint 3
Solution
Code

1904F - Beautiful Tree

Hint

<spoiler summary="Solution>

Lets rewrite the condition that node $$$a$$$ must be smaller than node $$$b$$$ as a directed edge from $$$a$$$ to $$$b$$$. Then, we can assign each node a value based on the topological sort of this new directed graph. If this directed graph had a cycle, it is clear that there is no way to order the nodes.

With this in mind, we can try to construct a graph that would have these properties. Once we have the graph, we can topological sort to find the answer.

For now, let's consider the problem if it only had type 1 requirements (type 2 requirements can be done very similarly).

Thus, the problem reduces to "given a path and a node, add a directed edge from the node to every node in that path." To do this, we can use binary lifting. For each node, create $$$k$$$ dummy nodes, the $$$i$$$th of which represents the minimum number from the path between node $$$a$$$ and the $$$2^i$$$th parent of $$$a$$$. Now, we can draw a directed edge from the the $$$i$$$th dummy node of $$$a$$$ to the $$$i-1$$$th dummy node of $$$a$$$ and the $$$i-1$$$th dummy node of the $$$2^{i-1}$$$th parent of $$$a$$$.

Now, to add an edge from any node to a vertical path of the tree, we can repeatedly add an edge from that node to the largest node we can. This will add $$$O(\log n)$$$ edges per requirement.

The final complexity is $$$O((n+m)\log n)$$$ time and $$$O((n+m)\log n)$$$.

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll ceil0(ll a, ll b) {
    return a / b + ((a ^ b) > 0 && a % b);
}

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

const int MAXN = 200'000;
const int LG = 18;
const int MAXM = 200'000;

vector<int> g[MAXN + 5];
int sz[MAXN + 5], in[MAXN + 5], par[MAXN + 5], depth[MAXN + 5], head[MAXN + 5], tim;
int n, m;

void dfs1(int x, int p){
    sz[x] = 1;
    for(int &i : g[x]){
        if(i == p) continue;
        dfs1(i, x);
        sz[x] += sz[i];
        if(g[x][0] == p || sz[i] > sz[g[x][0]]) swap(g[x][0], i);
    }
}
 
void dfs2(int x, int p){
    in[x] = tim++;
    par[x] = p;
    depth[x] = depth[p] + 1;
    for(int i : g[x]){
        if(i == p) continue;
        head[i] = (i == g[x][0] ? head[x] : i);
        dfs2(i, x);
    }
}

const int MAXSZ = MAXN + 2*MAXN*LG;
int down[LG][MAXN + 5];
int up[LG][MAXN + 5];
vector<int> dag[MAXSZ+ 5];
int lg[MAXN + 5];

void upd(int l, int r, int x, int t){
    if(l <= in[x] && in[x] <= r){
        if(l < in[x]) upd(l, in[x] - 1, x, t);
        if(in[x] < r) upd(in[x] + 1, r, x, t);
    } else {
        int sz = lg[r - l + 1];
        if(t == 2){
            dag[up[sz][l]].pb(x);
            dag[up[sz][r - (1 << sz) + 1]].pb(x);
        } else {
            dag[x].pb(down[sz][l]);
            dag[x].pb(down[sz][r - (1 << sz) + 1]);
        }
    }
}

//1 is down, 2 is up
void draw(int a, int b, int c, int t){
    while(head[a] != head[b]){
        if(depth[head[a]] > depth[head[b]]) swap(a, b);
        upd(in[head[b]], in[b], c, t);
        b = par[head[b]];
    }
    if(depth[a] > depth[b]) swap(a, b);
    upd(in[a], in[b], c, t);
}

bool vis[MAXSZ + 5], stk[MAXSZ + 5];
vector<int> ord;
bool fail;
int ind;

void dfs3(int x){
    if(fail) return;
    vis[x] = stk[x] = true;
    for(int i : dag[x]){
        if(i == x) continue;
        if(!vis[i]){
            dfs3(i);
        } else if(stk[i]){
            fail = true;
            break;
        }
    }
    stk[x] = false;
    if(x <= n) ord.pb(x);
}

int main(){
    setIO();
    cin >> n >> m;
    lg[1] = 0;
    for(int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    tim = 0;
    dfs1(1, 1);
    head[1] = 1;
    dfs2(1, 1);
    for(int i = 1; i <= n; i++) down[0][in[i]] = up[0][in[i]] = i;
    ind = n + 1;
    for(int i = 1; i < LG; i++){
        for(int j = 0; j + (1 << i) <= n; j++){
            down[i][j] = ind++;
            up[i][j] = ind++;

            dag[down[i][j]].pb(down[i - 1][j]);
            dag[down[i][j]].pb(down[i - 1][j + (1 << (i - 1))]);

            dag[up[i - 1][j]].pb(up[i][j]);
            dag[up[i - 1][j + (1 << (i - 1))]].pb(up[i][j]);
        }
    }
    for(int i = 0; i < m; i++){
        int t, a, b, c;
        cin >> t >> a >> b >> c;
        draw(a, b, c, t);
    }
    fail = false;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            dfs3(i);
            if(fail) break;
        }
    }
    if(fail){
        cout << -1 << endl;
        return 0;
    }
    reverse(ord.begin(), ord.end());
    int ans[n + 1];
    for(int i = 0; i < ord.size(); i++){
        ans[ord[i]] = i + 1;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en30 English oursaco 2023-12-10 01:55:13 1 (published)
en29 English oursaco 2023-12-10 01:54:58 58 (saved to drafts)
en28 English oursaco 2023-12-09 21:54:07 0 (published)
en27 English oursaco 2023-12-09 21:53:02 96
en26 English oursaco 2023-12-09 21:51:23 32
en25 English oursaco 2023-12-09 21:45:35 4 Tiny change: 'ts on A :(\nWe hope yo' -> 'ts on A :(. We hope yo'
en24 English oursaco 2023-12-09 21:45:19 44
en23 English oursaco 2023-12-09 21:42:58 1 Tiny change: 'tests on A. :(\n\n[pr' -> 'tests on A :(\n\n[pr'
en22 English oursaco 2023-12-09 21:41:57 2 Tiny change: 'em:1904D1]/[problem:1' -> 'em:1904D1] / [problem:1'
en21 English oursaco 2023-12-09 21:41:27 8
en20 English oursaco 2023-12-09 21:41:00 36
en19 English oursaco 2023-12-09 21:40:12 12
en18 English oursaco 2023-12-09 21:39:56 13
en17 English oursaco 2023-12-09 21:38:33 17
en16 English oursaco 2023-12-09 21:38:21 8
en15 English oursaco 2023-12-09 21:37:47 6
en14 English oursaco 2023-12-09 21:37:18 22
en13 English oursaco 2023-12-09 21:36:16 815
en12 English oursaco 2023-12-09 21:30:42 20
en11 English oursaco 2023-12-09 21:30:11 8
en10 English oursaco 2023-12-09 21:29:25 51
en9 English oursaco 2023-12-09 21:28:04 2 Tiny change: '="Solution>\nLet's b' -> '="Solution">\nLet's b'
en8 English oursaco 2023-12-09 21:27:03 1 Tiny change: 'iler>\n\n</spoiler>\n\n```\n#in' -> 'iler>\n\n<spoiler summary="Solution">\n```\n#in'
en7 English oursaco 2023-12-09 21:26:23 6 Tiny change: 'oiler>\n\n\n<spoil' -> 'oiler>\n\n<spoil'
en6 English oursaco 2023-12-09 21:25:49 3120
en5 English oursaco 2023-12-09 21:22:29 30
en4 English oursaco 2023-12-09 21:20:00 70
en3 English oursaco 2023-12-09 21:19:23 24709
en2 English oursaco 2023-12-09 20:23:24 118 Tiny change: 'e' -> '\[problem:1904A]'
en1 English oursaco 2023-12-09 19:35:39 40 Initial revision (saved to drafts)