제출 #216419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216419		usachevd0	Bridges (APIO19_bridges)	C++14	13 / 100	76 ms	7672 KiB

bridges

#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;
}

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