Submission #216419

#TimeUsernameProblemLanguageResultExecution timeMemory
216419usachevd0Bridges (APIO19_bridges)C++14
13 / 100
76 ms7672 KiB
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define time(...) 42
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

const int maxV = 50004;
const int maxE = 100005;
const int maxQ = 100005;
int eV[maxE], eU[maxE], eF[maxE];
int qT[maxQ], qI[maxE], qF[maxE];
vector<pii> G[maxV];

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        cin >> eV[i] >> eU[i] >> eF[i];
    }
    int Q;
    cin >> Q;
    for (int t = 1; t <= Q; ++t)
    {
        cin >> qT[t] >> qI[t] >> qF[t];
    }
    if (N <= 1000 && M <= 1000 && Q <= 10000)
    {
        for (int i = 1; i <= M; ++i)
        {
            int v = eV[i];
            int u = eU[i];
            G[v].emplace_back(u, i);
            G[u].emplace_back(v, i);
        }
        bool used[N + 1];
        function< int(int, int) > dfs = [&](int v, int my_f) -> int
        {
            used[v] = true;
            int sz = 1;
            for (pii p : G[v])
            {
                int u = p.fi;
                int f = eF[p.se];
                if (my_f <= f)
                {
                    if (!used[u])
                    {
                        sz += dfs(u, my_f);
                    }
                }
            }
            return sz;
        };
        for (int t = 1; t <= Q; ++t)
        {
            if (qT[t] == 1)
                eF[qI[t]] = qF[t];
            else
            {
                int v0 = qI[t];
                int my_f = qF[t];
                memset(used, 0, sizeof(used));
                cout << dfs(v0, my_f) << '\n';
            }
        }
        exit(0);
    }

    return 0;
}
#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...