oj.uz

Submission #237311

# Submission time Handle Problem Language Result Execution time Memory
237311 2020-06-05T20:57:17 Z jhnah917 Bridges (APIO19_bridges) C++14
13 / 100
 142 ms 8340 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct Edge{
    int s, e, x, i;
    Edge(int s, int e, int x, int i) : s(s), e(e), x(x), i(i) {}
    Edge() : Edge(0, 0, 0, 0) {}
    bool operator < (const Edge &t) const {
        return i < t.i;
    }
};

int n, m, q;
vector<Edge> g[50505];
Edge edge[101010]{};

void subtask1(){
    set<Edge> st[1010];
    int chk[1010] = {0};
    for(int i=1; i<=n; i++) st[i] = set<Edge>(all(g[i]));
    while(q--){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1){
            Edge &now = edge[a];
            st[now.s].erase(st[now.s].lower_bound(Edge(-1, -1, -1, a)));
            st[now.e].erase(st[now.e].lower_bound(Edge(-1, -1, -1, a)));
            now.x = b;
            st[now.s].insert(now);
            st[now.e].emplace(now.e, now.s, now.x, now.i);
        }else{
            memset(chk, 0, sizeof chk);
            queue<int> que; que.push(a); chk[a] = 1;
            int ans = 0;
            while(!que.empty()){
                int now = que.front(); que.pop();
                ans++;
                for(auto i : st[now]){
                    if(chk[i.e]) continue;
                    if(i.x < b) continue;
                    chk[i.e] = 1;
                    que.push(i.e);
                }
            }
            cout << ans << "\n";
        }
    }
}

const unsigned sz = 1u << 17u;
struct Sub2_Seg{
    int tree[1u << 18u]{};
    Sub2_Seg(){ memset(tree, 0x3f, sizeof tree); }
    void update(unsigned x, int v){
        x |= sz; tree[x] = v;
        while(x >>= 1u) tree[x] = min(tree[x << 1u], tree[x << 1u | 1u]);
    }
    int query(unsigned l, unsigned r){
        l |= sz; r |= sz;
        int ret = tree[0];
        while(l <= r){
            if(l & 1u) ret = min(ret, tree[l++]);
            if(~r & 1u) ret = min(ret, tree[r--]);
            l >>= 1u; r >>= 1u;
        }
        return ret;
    }
};

void subtask2(){
    Sub2_Seg seg;
    for(int i=1; i<n; i++){
        seg.update(i, edge[i].x);
    }
    while(q--){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1) seg.update(a, b);
        else{
            int left = a, right = a;
            int l = 1, r = a;
            while(l < r){
                int mid = (l + r) / 2;
                if(mid == a) break;
                if(seg.query(mid, a-1) < b) l = mid + 1;
                else r = mid;
            }
            left = r;
            l = a, b = n-1;
            while(l < r){
                int mid = (l + r + 1) / 2;
                if(seg.query(a, mid) < b) r = mid - 1;
                else l = mid;
            }
            right = l + 1;
            if(seg.query(a, a) < b) right = a;
            for(int i=max(1, left-5); i<a; i++){
                if(seg.query(i, a-1) >= b){ left = i; break; }
            }
            for(int i=min(n-1, right+5); i>=a; i--){
                if(seg.query(a, i) >= b){ right = i+1; break; }
            }
            cout << right - left + 1 << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    bool is_2 = true;
    cin >> n >> m;
    if(m != n-1) is_2 = false;
    for(int i=0; i<m; i++){
        int s, e, x; cin >> s >> e >> x;
        g[s].emplace_back(s, e, x, i+1);
        g[e].emplace_back(e, s, x, i+1);
        edge[i+1] = {s, e, x, i+1};
        if(s != i+1 && e != i+2) is_2 = false;
    }
    cin >> q;
    if(n <= 1000 && m <= 1000 && q <= 10000){
        subtask1(); return 0;
    }
    if(is_2){
        subtask2(); return 0;
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 142 ms 3328 KB Output is correct
4 Correct 13 ms 3200 KB Output is correct
5 Correct 22 ms 3200 KB Output is correct
6 Correct 23 ms 3200 KB Output is correct
7 Correct 18 ms 3200 KB Output is correct
8 Correct 16 ms 3200 KB Output is correct
9 Correct 24 ms 3200 KB Output is correct
10 Correct 14 ms 3200 KB Output is correct
11 Correct 13 ms 3200 KB Output is correct
12 Correct 13 ms 3200 KB Output is correct
13 Correct 18 ms 3200 KB Output is correct
14 Correct 16 ms 3200 KB Output is correct
15 Correct 18 ms 3200 KB Output is correct
16 Correct 18 ms 3248 KB Output is correct
17 Correct 17 ms 3200 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 6648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 8340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 6648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 142 ms 3328 KB Output is correct
4 Correct 13 ms 3200 KB Output is correct
5 Correct 22 ms 3200 KB Output is correct
6 Correct 23 ms 3200 KB Output is correct
7 Correct 18 ms 3200 KB Output is correct
8 Correct 16 ms 3200 KB Output is correct
9 Correct 24 ms 3200 KB Output is correct
10 Correct 14 ms 3200 KB Output is correct
11 Correct 13 ms 3200 KB Output is correct
12 Correct 13 ms 3200 KB Output is correct
13 Correct 18 ms 3200 KB Output is correct
14 Correct 16 ms 3200 KB Output is correct
15 Correct 18 ms 3200 KB Output is correct
16 Correct 18 ms 3248 KB Output is correct
17 Correct 17 ms 3200 KB Output is correct
18 Incorrect 121 ms 6648 KB Output isn't correct
19 Halted 0 ms 0 KB -