제출 #987813

#제출 시각아이디문제언어결과실행 시간메모리
987813876pol다리 (APIO19_bridges)C++17
29 / 100
3048 ms22096 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; using ll = long long; using int128 = __int128_t; using pll = pair<ll, ll>; template <class T> using vec = vector<T>; template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++) #define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++) #define TRAV(e, a) for (const auto &e : a) #define all(x) x.begin(), x.end() #define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl; template <class T, class = decay_t<decltype(*begin(declval<T>()))>, class = enable_if_t<!is_same<T, string>::value>> ostream &operator<<(ostream &out, const T &obj) { out << "["; for (auto it = obj.begin(); it != obj.end(); it++) { out << &", "[2 * (it == obj.begin())] << *it; } return out << "]"; } template <class K, class V> ostream &operator<<(ostream &out, const pair<K, V> &obj) { return out << "(" << obj.first << ", " << obj.second << ")"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); bool st2 = true, st4 = true; ll n, m; cin >> n >> m; st2 &= (m == n - 1); vec<vec<pll>> graph(n + 1); vec<ll> w(m + 1); CFOR(i, 1, m) { ll a, b; cin >> a >> b >> w[i]; graph[a].push_back({b, i}); graph[b].push_back({a, i}); st2 &= (a + 1 == b); } ll q; cin >> q; vec<vec<ll>> queries(q, vec<ll>(4)); FOR(i, 0, q) { cin >> queries[i][0] >> queries[i][1] >> queries[i][2]; queries[i][3] = i; st4 &= (queries[i][0] == 2); } if (st2) { const ll SZ = 3; vec<ll> b(n / SZ + 1, 1e9); CFOR(i, 0, n - 1) b[i / SZ] = min(b[i / SZ], w[i]); FOR(i, 0, q) { if (queries[i][0] == 1) { ll bind = queries[i][1] / SZ; w[queries[i][1]] = queries[i][2]; b[bind] = 1e9; FOR(i, bind * SZ, min((bind + 1) * SZ, n)) { b[bind] = min(b[bind], w[i]); } } else { ll bind = queries[i][1] / SZ; if (queries[i][2] > b[bind]) { ll l = queries[i][1], r = queries[i][1]; while (1 < l && w[l - 1] >= queries[i][2]) l--; while (r < n && w[r] >= queries[i][2]) r++; cout << r - l + 1 << "\n"; } else { ll bl = bind, br = bind; while (0 < bl && b[bl - 1] >= queries[i][2]) bl--; while (br < b.size() && b[br] >= queries[i][2]) br++; ll l = bl * SZ; ll r = min(br * SZ, n); while (1 < l && w[l - 1] >= queries[i][2]) l--; while (r < n && w[r] >= queries[i][2]) r++; cout << r - l + 1 << "\n"; } } } } else if (st4) { sort(all(queries), [&](const vec<ll> &o1, const vec<ll> &o2) { return o1[2] > o2[2]; }); vec<ll> parent(n + 1), sz(n + 1, 1); iota(all(parent), 0ll); function<ll(ll)> find = [&](ll x) -> ll { if (x != parent[x]) parent[x] = find(parent[x]); return parent[x]; }; function<void(ll, ll)> unify = [&](ll x, ll y) { x = find(x); y = find(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); if (graph[y].size() > graph[x].size()) swap(graph[x], graph[y]); parent[y] = x; sz[x] += sz[y]; TRAV(e, graph[y]) { if (find(x) != find(e.first)) graph[x].push_back(e); } }; vec<ll> ans(q); FOR(i, 0, q) { set<ll> visited; function<void(ll)> dfs = [&](ll curr) { visited.insert(curr); TRAV(e, graph[curr]) { if (visited.count(find(e.first)) || queries[i][2] > w[e.second]) continue; dfs(find(e.first)); } }; dfs(find(queries[i][1])); TRAV(e, visited) unify(e, *visited.begin()); ans[queries[i][3]] = sz[find(queries[i][1])]; } TRAV(e, ans) cout << e << "\n"; } else { vec<bool> visited(n + 1); FOR(i, 0, q) { if (queries[i][0] == 1) { w[queries[i][1]] = queries[i][2]; } else { fill(all(visited), 0ll); function<void(ll)> dfs = [&](ll curr) { visited[curr] = 1; TRAV(e, graph[curr]) { if (visited[e.first] || queries[i][2] > w[e.second]) continue; dfs(e.first); } }; dfs(queries[i][1]); cout << accumulate(all(visited), 0ll) << "\n"; } } } }

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

bridges.cpp: In function 'int main()':
bridges.cpp:85:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                     while (br < b.size() && b[br] >= queries[i][2]) br++;
      |                            ~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...