oj.uz

Submission #991317

# Submission time Handle Problem Language Result Execution time Memory
991317 2024-06-02T01:25:04 Z saddd Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 239 ms 91264 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//#pragma GCC optimize("O3")
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 5e5 + 5, mxq = 1e5 + 5, sq = 1005, mxv = 5e4 + 1, lg = 60;
//const int base = (1 <<18);
const ll inf = 2e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!;
int n, k;
struct ST{
    int type, st[4 * mxn + 1];
    void init(int _type){
        type = _type; //0: max, 1: min 
        if(type){
            for(int i = 1; i <= 4 * n; i++)st[i] = inf;
            
        }else{
             for(int i = 1; i <= 4 * n; i++)st[i] = -1;
        }
    }
    int comb0(int a, int b){
        return(max(a, b));
    }
    int comb1(int a, int b){
        return(min(a, b));
    }
    void upd(int nd, int l, int r, int ql, int qr, int v){
        //cout << ql << " " << qr << "\n";
        if(ql > r || qr < l)return;
        if(ql <= l && qr >= r){
            if(!type)st[nd] = comb0(st[nd], v); 
            else st[nd] = comb1(st[nd], v);
            //cout << st[nd] << " ";
            return;
        }
        int mid = (l + r) >> 1;
        upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
    }
    int get(int nd, int l, int r, int id, int v){
        if(!type)v = comb0(v, st[nd]);
        else v = comb1(v, st[nd]);
        if(l == r)return(v);
        int mid = (l + r) >> 1;
        if(id <= mid)return(get(nd << 1, l, mid, id, v));
        else return(get(nd << 1 | 1, mid + 1, r, id, v));
    }
};
int siz[mxn + 1], pa[mxn + 1], tin[mxn + 1], tt = 0, dep[mxn + 1], head[mxn + 1];
vt<int>adj[mxn + 1];
ST stmx, stmn;
void dfs(int s, int pre){
    siz[s] = 1; pa[s] = pre;
    for(auto i: adj[s]){
        if(i != pre){
            dep[i] = dep[s] + 1;
            dfs(i, s); siz[s] += siz[i];
        }
    }
}
void hld(int s, int pre, int group){
    head[s] = group; tin[s] = ++tt;
    int mx = 0, son = -1; 
    for(auto i: adj[s]){
        if(i != pre){
            if(siz[i] > mx){
                mx = siz[i]; son = i;
            }
        }
    }
    if(!mx)return;
    hld(son, s, group);
    for(auto i: adj[s]){
        if(i != pre && i != son){
            hld(i, s, i);
        }
    }
}
void upd(int u, int v, int x, bool type){
    while(head[u] != head[v]){
        if(dep[head[u]] < dep[head[v]])swap(u, v);
        if(!type)stmn.upd(1, 1, n, tin[head[u]], tin[u], x);
        else stmx.upd(1, 1, n, tin[head[u]], tin[u], x);
        u = pa[head[u]];
    }
    if(tin[u] > tin[v])swap(u, v);
    if(!type)stmn.upd(1, 1, n, tin[u] + 1, tin[v], x);
    else stmx.upd(1, 1, n, tin[u] + 1, tin[v], x);
}
struct th{
    ll u, v, cap, flow;
};
struct Dinic{
    vt<int>level, to;
    int id = 0, curr, s, t;
    vt<vt<int>>adj;
    vt<th>edge;
    void init(int st, int en, int n){
        adj.resize(n); to.resize(n); level.resize(n); s = st; t = en;
    }
    void add_edge(int u, int v, int cap){
        adj[u].pb(id); adj[v].pb(id + 1); 
        edge.pb({u, v, cap, 1LL * 0}); edge.pb({v, u, cap, 1LL * 0});
        id += 2;
    }
    bool bfs(){
        fill(level.begin(), level.end(), -1);
        fill(to.begin(), to.end(), 0);
        level[s] = 0;
        queue<int>q; q.push(s);
        
        while(!q.empty()){
            
            int nw = q.front(); q.pop(); //cout << nw << " ";
            if(nw == t)return(true);
            for(auto i: adj[nw]){
                int v = edge[i].v; 
                if(level[v] != -1 || edge[i].flow + curr - 1 >= edge[i].cap)continue;
                level[v] = level[nw] + 1;
                q.push(v);
            }
        }
        return(level[t] != -1);
    }
    int dfs(int u, ll f){
        if(u == t)return(f);
        if(!f)return(0);
        for(int &eid = to[u]; eid < adj[u].size(); eid++){
            int cr = adj[u][eid];
            if(level[edge[cr].v] != level[u] + 1)continue;
            if(edge[cr].flow == edge[cr].cap)continue;
            ll nwf = dfs(edge[cr].v, min(f, edge[cr].cap - edge[cr].flow));
            if(!nwf)continue;
            edge[cr].flow += nwf; edge[cr ^ 1].flow  -= nwf;
            return(nwf);
        }
        return(0);
    }
    int flow(){
        int res = 0;
        for(curr = 1 << 30; curr; curr >>= 1){
            
            while(bfs()){
                for(int f = dfs(s, inf); f; f = dfs(s, inf))res += f;
            }
        }
        return(res);
    }
};
Dinic d;
int lv[mxn + 1], rv[mxn + 1], idl[mxn + 1], idr[mxn + 1];
vt<pii>edge;
map<int, int>mp;
void solve(){  
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u); edge.pb(mpp(u, v));
    }
    dfs(1, -1); hld(1, -1, 1);
    cin >> k;
    stmx.init(0); stmn.init(1);
    for(int i = 0; i < k; i++){
        char c; cin >> c;
        int u, v, x; cin >> u >> v >> x; mp[x] = i;
        upd(u, v, x, (c == 'm'));
    }
    d.init(0, n + k + 1, n + k + 2);
    for(int i = 0; i < n - 1; i++){
        auto [u, v] = edge[i]; if(tin[u] < tin[v])swap(u, v);
        lv[i] = stmx.get(1, 1, n, tin[u], -1); rv[i] = stmn.get(1, 1, n, tin[u], inf);
        //cout << lv[i] << " " << rv[i] << "\n";
        d.add_edge(0, i + 1, 1);
        if(lv[i] != -1){
            
            idl[i] = d.id; d.add_edge(i + 1, n + mp[lv[i]] + 1, 1); 
        }if(rv[i] != inf){
            idr[i] = d.id; d.add_edge(i + 1, n + mp[rv[i]] + 1, 1);
        }
    }
    for(int i = 0; i < k; i++){
        d.add_edge(n + i + 1, n + k + 1, 1);
    }
    d.flow();
    for(int i = 0; i < n - 1; i++){
        cout << edge[i].fi << " " << edge[i].se << " "; 
        if(lv[i] == -1 && rv[i] == inf)cout << 69420 << "\n";
        else if(lv[i] != -1 && (d.edge[idl[i]].flow || rv[i] == inf))cout << lv[i] << "\n";
        else cout << rv[i] << "\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("TESTROOMS.inp", "r", stdin);
    //freopen("TESTROOMS.out", "w", stdout);
    int tt; tt = 1;
    while(tt--){
        solve();

    }
    return(0);
}

Compilation message

minmaxtree.cpp: In member function 'int Dinic::dfs(int, long long int)':
minmaxtree.cpp:148:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int &eid = to[u]; eid < adj[u].size(); eid++){
      |                               ~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 71284 KB Output is correct
2 Correct 170 ms 67764 KB Output is correct
3 Correct 142 ms 68260 KB Output is correct
4 Correct 177 ms 72780 KB Output is correct
5 Correct 148 ms 69588 KB Output is correct
6 Correct 152 ms 69568 KB Output is correct
7 Correct 142 ms 69304 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 61780 KB Output is correct
2 Correct 115 ms 62904 KB Output is correct
3 Correct 90 ms 57276 KB Output is correct
4 Correct 92 ms 58644 KB Output is correct
5 Correct 116 ms 64352 KB Output is correct
6 Correct 121 ms 64444 KB Output is correct
7 Correct 121 ms 63660 KB Output is correct
8 Correct 118 ms 62500 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29020 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 181 ms 71284 KB Output is correct
6 Correct 170 ms 67764 KB Output is correct
7 Correct 142 ms 68260 KB Output is correct
8 Correct 177 ms 72780 KB Output is correct
9 Correct 148 ms 69588 KB Output is correct
10 Correct 152 ms 69568 KB Output is correct
11 Correct 142 ms 69304 KB Output is correct
12 Correct 104 ms 61780 KB Output is correct
13 Correct 115 ms 62904 KB Output is correct
14 Correct 90 ms 57276 KB Output is correct
15 Correct 92 ms 58644 KB Output is correct
16 Correct 116 ms 64352 KB Output is correct
17 Correct 121 ms 64444 KB Output is correct
18 Correct 121 ms 63660 KB Output is correct
19 Correct 118 ms 62500 KB Output is correct
20 Correct 212 ms 68408 KB Output is correct
21 Correct 179 ms 67168 KB Output is correct
22 Correct 164 ms 67336 KB Output is correct
23 Correct 174 ms 66256 KB Output is correct
24 Correct 238 ms 89524 KB Output is correct
25 Correct 228 ms 91264 KB Output is correct
26 Correct 239 ms 88848 KB Output is correct
27 Correct 199 ms 87464 KB Output is correct
28 Correct 200 ms 69808 KB Output is correct
29 Correct 201 ms 69804 KB Output is correct
30 Correct 223 ms 66652 KB Output is correct
31 Correct 201 ms 68508 KB Output is correct
32 Correct 226 ms 69564 KB Output is correct
33 Correct 190 ms 67880 KB Output is correct
34 Correct 186 ms 67764 KB Output is correct
35 Correct 202 ms 67220 KB Output is correct