Submission #1259281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259281		herominhsteve	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	53 ms	17472 KiB

minmaxtree

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 7e4+5;
const int INF = 3e9 + 15092007;

struct Query{
    bool type; // ! 0/1 m/M
    int u,v;
    long long w;
    Query(char x='#',int U=0,int V=0,long long W=0){
        type = (x=='M' ? 1 : 0);
        u=U;
        v=V;
        w=W;
    }
};

int n,q;
vector<int> graph[MAXN];
vector<Query> query;
map<int,int> queryID;
int uID[MAXN],vID[MAXN];

struct Hopcorft{
    int nL,nR;
    vector<vector<int>> graph;
    vector<int> matchLeft,matchRight;
    vector<int> distancia;
    queue<int> qu;
    Hopcorft(int l,int r): nL(l),nR(r){
        graph.resize(nL+1);
        matchLeft.assign(nL+1,0);
        matchRight.assign(nR+1,0);
        distancia.assign(nL+1,0);
    }
    void addEdge(int u,int v){
        graph[u].push_back(v);
    }
    bool bfs(){
        for (int u=1;u<=nL;u++){
            if (!matchLeft[u]){
                distancia[u]=0;
                qu.push(u);
            } else distancia[u] = INF;
        }
        distancia[0]=INF;
        while (!qu.empty()){
            int u = qu.front(); qu.pop();
            if (distancia[u]>=distancia[0]) continue;
            for (int v :graph[u]){
                if (distancia[matchRight[v]]==INF){
                    distancia[matchRight[v]] = distancia[u] + 1;
                    qu.push(matchRight[v]);
                }
            }
        }
        return (distancia[0]!=INF);
    }
    bool dfs(int u){
        if (!u) return true;
        for (int v : graph[u]){
            if (distancia[matchRight[v]]==distancia[u]+1 and dfs(matchRight[v])){
                matchRight[v] = u;
                matchLeft[u] = v;
                return true;
            }
        }
        distancia[u] = INF;
        return false;
    }
    int maxMatching(){
        int match=0;
        while (bfs()){
            for (int u=1;u<=nL;u++){
                if (!matchLeft[u] and dfs(u)) match++;
            }
        }
        return match;
    }
    void getW(vector<int> &res){
        maxMatching();
        for (int u=1;u<=nL;u++){
            if (matchLeft[u]) res[matchLeft[u]] = query[u].w;
        }
    }
};

// ! Sweepline part
vector<pair<int,int>> eventA[MAXN], eventR[MAXN];

inline void rangeAddEvent(int l,int r,int w,int type){
    if (l>r) return;
    eventA[l].emplace_back(w,type);
    eventR[r].emplace_back(w,type);
}

// ! HLD
int timedfs=1, curChain=1,edgecnt=0;
int eID[MAXN]; // ! edge: parent[u] - u
int parent[MAXN];
int pos[MAXN],arr[MAXN];

namespace HeavyLight{
    vector<int> chainHead,chainID;
    vector<int> depth,sz;

    void dfs(int u,int pre){
        parent[u] = pre;
        for (int v:graph[u]){
            if (v^pre){
                depth[v] = depth[u] + 1;
                dfs(v,u);
                sz[u] += sz[v];
            }
        }
    }

    void HLD(int u,int pre){
        if (!chainHead[curChain]){
            chainHead[curChain] = u;
        }
        chainID[u] = curChain;
        pos[u] = timedfs;
        arr[timedfs] = u;
        timedfs++;

        if (u==pre) eID[u] = 0;
        else {
            eID[u] = ++edgecnt;
        }

        int nxt=-1;
        for (int v:graph[u]){
            if (v^pre){
                if (nxt==-1 or sz[v]>sz[nxt]){
                    nxt = v;
                }
            }
        }
        if (nxt) HLD(nxt,u);
        for (int v:graph[u]){
            if (v^pre and v^nxt){
                curChain++;
                HLD(v,u);
            }
        }
    }

    void addEvent(int u,int v,int w,int type){
        while (chainHead[chainID[u]] != chainHead[chainID[v]]){
            if (depth[chainHead[chainID[u]]] < depth[chainHead[chainID[v]]]) swap(u,v);
            rangeAddEvent(pos[chainHead[chainID[u]]],u,w,type);
            u = parent[chainHead[chainID[u]]];
        }
        if (depth[u] < depth[v]) swap(u,v);
        if (u^v) rangeAddEvent(pos[v]+1, pos[u],w,type);
    }

    void initHLD(){
        chainHead.assign(n+1,0);
        chainID.assign(n+1,0);
        depth.assign(n+1,0);
        sz.assign(n+1,1);
        dfs(1,1);
        HLD(1,1);
    }
};

using namespace HeavyLight;

void init(){
	cin>>n;
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        uID[i] = u;
        vID[i] = v;
    }
    cin>>q;
    query.resize(q+1);
    for (int i=1;i<=q;i++){
        char c;
        int u,v,w;
        cin>>c>>u>>v>>w;
        query[i] = Query(c,u,v,w);
        queryID[w] = i;
    }
}

void sol(){
	initHLD();
    for (int i=1;i<=q;i++) addEvent(query[i].u,query[i].v,query[i].w,query[i].type);
    vector<int> maxOfMin(n,-INF), minOfMax(n,INF);
    multiset<int> activeMin,activeMax;
    
    for (int curtime=1;curtime<=n;curtime++){
        // ! start sweeping
        for (pair<int,int> ev : eventA[curtime]){
            if (ev.second) activeMax.insert(ev.first);
            else activeMin.insert(ev.first);
        }
        int u = arr[curtime];
        int e = eID[u];
        if (e){
            if (!activeMax.empty()) minimize(minOfMax[e],*activeMax.rbegin());
            if (!activeMin.empty()) maximize(maxOfMin[e],*activeMin.begin());
        }
        for (pair<int,int> ev: eventR[curtime]){
            if (ev.second){
                multiset<int>::iterator it = activeMax.find(ev.first);
                if (it!=activeMax.end()) activeMax.erase(it);
            } else{
                multiset<int>::iterator it = activeMin.find(ev.first);
                if (it!=activeMin.end()) activeMin.erase(it);
            }
        }
    }

    Hopcorft karp(q,n-1);
    for (int e=1;e<n;e++){
        if (maxOfMin[e]!=-INF){
            map<int,int>::iterator it = queryID.find(maxOfMin[e]);
            karp.addEdge((*it).second,e);
        }
        if (minOfMax[e]!=INF and minOfMax[e]!=maxOfMin[e]){
            map<int,int>::iterator it = queryID.find(minOfMax[e]);
            karp.addEdge((*it).second,e);
        }
    }
    vector<int> res(n,0);
    for (int e=1;e<n;e++){
        int val = 0;
        maximize(val,maxOfMin[e]);
        minimize(val,minOfMax[e]);
        res[e] = val;
    }
    karp.getW(res);
    map<pair<int,int>,int> toEID;
    function<pair<int,int>(int,int)> uv = [&] (int u,int v) -> pair<int,int> {
        if (u>v) swap(u,v);
        return make_pair(u,v);
    };
    for (int v=2;v<=n;v++){
        int u = parent[v];
        toEID[uv(u,v)] = eID[v];
    }
    for (int e=1;e<n;e++){
        int u = uID[e];
        int v = vID[e];
        cout<<u<<" "<<v<<" "<<res[toEID[uv(u,v)]]<<el;
    }
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

minmaxtree.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '3.015092007e+9' to '2147483647' [-Woverflow]
   22 | const int INF = 3e9 + 15092007;
      |                 ~~~~^~~~~~~~~~
minmaxtree.cpp: In function 'void setup()':
minmaxtree.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42