Submission #335843

#	Time	Username	Problem	Language	Result	Execution time	Memory
335843		LifeHappen__	Bridges (APIO19_bridges)	C++14	13 / 100	88 ms	7148 KiB

bridges

#define TASK "limit"

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <utility>
#include <cctype>
using namespace std;

template<typename A, typename B>ostream& operator<<(ostream& os, const pair<A,B>& p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream& os, const T_container& v) { os << '('; string sep; for(const T& x : v) os << sep << x, sep = ", "; return os << ")\n"; }
#ifdef DBG
void dbgout() {cerr << endl;}
template<typename Head, typename... Tail> void dbgout(const Head& h, Tail... t) { cerr << ' ' << h; dbgout(t...); }
#define dbg(...) cerr << '(' << #__VA_ARGS__ << "):", dbgout(__VA_ARGS__)
#else
#define dbg(...)
#endif // DBG

#define readInt() ({char c; bool neg = false; for(c=getchar(); !isdigit(c) && (c!='-'); c=getchar()); if(c=='-')neg=true, c=getchar(); int64_t num=c-'0'; for(c=getchar();isdigit(c); c=getchar())num=(num<<1)+(num<<3)+c-'0'; neg?-num:num;})

const int maxn = 50005;
int n, m, q, now = 0;
vector<int> adj[maxn];
array<int, 3> edges[maxn << 1];

int vis[maxn];

void dfs(int u, int w) {
   vis[u] = now;
   for (int i : adj[u]) {
      int v = edges[i][0] == u ? edges[i][1] : edges[i][0];
      int lim = edges[i][2];
      if (vis[v] != now && w <= lim)
         dfs(v, w);
   }
}

void sub1(){
   while (q --> 0){
      int type, x, y;
      cin >> type >> x >> y;
      if (type == 1){
         edges[x][2] = y;
      }
      else {
         ++now;
         dfs(x, y);
         int ans = 0;
         for (int u = 1; u <= n; ++u)
            if (vis[u] == now)
               ans++;
         cout << ans << '\n';
      }
   }
}

int main(){
   ios_base::sync_with_stdio(false);
#ifndef DBG
   cin.tie(nullptr);
   //freopen(TASK".out", "w", stdout);
#endif // DBG
   //freopen(TASK".inp", "r", stdin);

   cin >> n >> m;

   for (int i = 1; i <= m; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      adj[u].push_back(i);
      adj[v].push_back(i);
      edges[i] = {u, v, w};
   }

   cin >> q;

   if (max(n, m) * 1ll * q <= int(1e7))
      sub1();


   return 0;
}

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