oj.uz

Submission #237313

# Submission time Handle Problem Language Result Execution time Memory
237313 2020-06-05T21:24:50 Z jhnah917 Bridges (APIO19_bridges) C++14
13 / 100
 133 ms 8312 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 int sz = 1u << 17u;
struct Sub2_Seg{
    int tree[1 << 18];
    Sub2_Seg(){ memset(tree, 0x3f, sizeof tree); }
    void update(int x, int v, int node = 1, int s = 1, int e= n-1){
        if(s == e){ tree[node] = v; return; }
        int mid = (s + e) >> 1;
        if(x <= mid) update(x, v, node << 1, s, mid);
        else update(x, v, node << 1 | 1, mid + 1, e);
        tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
    }
    int queryL(int x, int v, int node = 1, int s = 1, int e = n-1){
        if(x < s) return 0;
        if(s == e){
            if(tree[node] >= v) return 0;
            else return s;
        }
        if(e <= x && tree[node] >= v) return 0;
        int mid = (s + e) >> 1;
        if(queryL(x, v, node << 1 | 1, mid+1, e)) return x;
        return queryL(x, v, node << 1, s, mid);
    }
    int queryR(int x, int v, int node = 1, int s = 1, int e = n-1){
        if(e < x) return n;
        if(s == e){
            if(tree[node] >= v) return n;
            else return s;
        }
        if(x <= s && tree[node] >= v) return n;
        int mid = (s + e) >> 1;
        if(queryR(x, v, node << 1, s, mid) != n) return x;
        return queryR(x, v, node << 1 | 1, mid+1, e);
    }
};

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 {
            cout << seg.queryR(a, b) - seg.queryL(a-1, b) << "\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 3072 KB Output is correct
3 Correct 133 ms 3328 KB Output is correct
4 Correct 12 ms 3200 KB Output is correct
5 Correct 21 ms 3200 KB Output is correct
6 Correct 20 ms 3200 KB Output is correct
7 Correct 18 ms 3072 KB Output is correct
8 Correct 16 ms 3200 KB Output is correct
9 Correct 23 ms 3200 KB Output is correct
10 Correct 13 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 17 ms 3200 KB Output is correct
16 Correct 18 ms 3200 KB Output is correct
17 Correct 18 ms 3200 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 6520 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 3072 KB Output is correct
3 Correct 133 ms 3328 KB Output is correct
4 Correct 12 ms 3200 KB Output is correct
5 Correct 21 ms 3200 KB Output is correct
6 Correct 20 ms 3200 KB Output is correct
7 Correct 18 ms 3072 KB Output is correct
8 Correct 16 ms 3200 KB Output is correct
9 Correct 23 ms 3200 KB Output is correct
10 Correct 13 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 17 ms 3200 KB Output is correct
16 Correct 18 ms 3200 KB Output is correct
17 Correct 18 ms 3200 KB Output is correct
18 Incorrect 96 ms 6520 KB Output isn't correct
19 Halted 0 ms 0 KB -