제출 #991317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991317		saddd	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	239 ms	91264 KiB

minmaxtree

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42