Submission #433712

#	Time	Username	Problem	Language	Result	Execution time	Memory
433712		someone	Bridges (APIO19_bridges)	C++14	13 / 100	605 ms	524292 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

struct Req {
    bool isQ;
    int id, w;
};

struct Arc {
    int sum, w;
};

struct Event {
    bool isQ;
    int w, deb, fin, pos, id;
};

struct Node {
    int deb, fin, mini;
};

const int M = 1 << 16, N = 2*M, INF = 1e9 + 42;

bool passe[N];
Node node[N];
vector<Req> req;
vector<Arc> arc;
vector<int> adj[N];
vector<Event> event;
int n, m, q, par[N], ans[N];

void setMin(int i, int newMin) {
    if(i == 0)
        return;
    if(i >= M) {
        node[i].mini = newMin;
    } else {
        node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
    }
    setMin(i/2, newMin);
}

int getMin(int i, int deb, int fin) {
    if(fin <= node[i].deb || node[i].fin <= deb)
        return INF;
    if(deb <= node[i].deb && node[i].fin <= fin) {
        return node[i].mini;
    }
    return min(getMin(i*2, deb, fin), getMin(i*2+1, deb, fin));
}

void DFS(int i, int w) {
    if(passe[i])
        return;
    passe[i] = true;
    for(int j : adj[i])
        if(arc[j].w >= w)
            DFS(arc[j].sum - i, w);
}

bool way(int deb, int fin, int w) {
    return getMin(1, deb, fin) >= w;
}

int possibleL(int deb, int fin, int w, int obj) {
    if(deb + 1 == fin)
        return deb;
    if(deb + 2 == fin) {
        if(way(deb, obj, w))
            return deb;
        return deb+1;
    }
    int med = (deb + fin) / 2;
    if(way(med-1, obj, w))
        return possibleL(deb, med, w, obj);
    return possibleL(med, fin, w, obj);
}

int possibleR(int deb, int fin, int w, int obj) {
    if(deb + 1 == fin)
        return deb;
    if(deb + 2 == fin) {
        if(way(obj, deb+1, w))
            return deb+1;
        return deb;
    }

    int med = (deb + fin) / 2;
    if(way(obj, med, w))
        return possibleR(med, fin, w, obj);
    return possibleR(deb, med, w, obj);
}

int Find(int i) {
    if(par[i] < 0)
        return i;
    return par[i] = Find(par[i]);
}

void Union(int a, int b) {
    a = Find(a), b = Find(b);
    if(a == b)
        return;
    if(par[a] > par[b])
        swap(a, b);
    par[a] += par[b];
    par[b] = a;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int e1, e2, w;
        cin >> e1 >> e2 >> w;
        e1--, e2--;
        adj[e1].push_back(i);
        adj[e2].push_back(i);
        arc.push_back({e1 + e2, w});
        event.push_back({false, w, e1, e2, -1, -1});
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        int type, id, w;
        cin >> type >> id >> w;
        id--;
        if(type == 2)
            req.push_back({true, id, w});
        else
            req.push_back({false, id, w});
        event.push_back({true, w, -1, -1, id, i});
    }
    if(n <= 1000 && m <= 1000 && q <= 10000) {
        for(int i = 0; i < q; i++) {
            if(req[i].isQ) {
                DFS(req[i].id, req[i].w);
                int nb = 0;
                for(int j = 0; j < n; j++)
                    if(passe[j]) {
                        nb++;
                        passe[j] = false;
                    }
                cout << nb << '\n';
            } else {
                arc[req[i].id].w = req[i].w;
            }
        }
        return 0;
    }
    bool t2 = true;
    for(int i = 0; i < q; i++)
        if(!req[i].isQ)
            t2 = false;

    if(!t2) {
        for(int i = M; i < N; i++) {
            node[i].deb = i - M;
            node[i].fin = i - M + 1;
            if(i >= n + M) {
                node[i].mini = INF;
            } else {
                node[i].mini = arc[i - M].w;
            }
        }
        for(int i = M-1; i > 0; i--) {
            node[i].deb = node[i*2].deb;
            node[i].fin = node[i*2+1].fin;
            node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
        }

        for(int i = 0; i < q; i++) {
            if(req[i].isQ) {
                int left = possibleL(0, req[i].id+1, req[i].w, req[i].id),
                    right = possibleR(req[i].id, n, req[i].w, req[i].id);
                cout << right - left + 1 << '\n';
            } else {
                setMin(req[i].id + M, req[i].w);
            }
        }
        return 0;
    }
    sort(event.begin(), event.end(),
    [](Event a, Event b) {
        if(a.w == b.w)
            return b.isQ;
        return a.w > b.w;
    });

    for(Event e : event) {
        if(e.isQ) {
            ans[e.id] = -par[Find(e.pos)];
        } else {
            Union(e.deb, e.fin);
        }
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27