oj.uz

Submission #646092

# Submission time Handle Problem Language Result Execution time Memory
646092 2022-09-28T15:49:41 Z pls33 Bridges (APIO19_bridges) C++17
13 / 100
 3000 ms 10508 KB 
#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;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;

using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;

template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

const int BUF_SZ = 1 << 15;
inline namespace fast_in
{
    char buf[BUF_SZ];
    int pos;
    int len;

    char next_char(FILE *f)
    {
        if (pos == len)
        {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, f);

            if (!len)
            {
                return EOF;
            }
        }

        return buf[pos++];
    }

    int read_int(FILE *f)
    {
        int x;
        char ch;
        int sgn = 1;

        while (!isdigit(ch = next_char(f)))
        {
            if (ch == '-')
            {
                sgn *= -1;
            }
        }

        x = ch - '0';
        while (isdigit(ch = next_char(f)))
        {
            x = x * 10 + (ch - '0');
        }

        return x * sgn;
    }
}

/**
 * @brief gale programos flush_out kviest!!
 */
inline namespace fast_out
{
    char buf[BUF_SZ];
    int pos;

    void flush_out(FILE *f)
    {
        fwrite(buf, 1, pos, f);
        pos = 0;
    }

    void write_char(char c, FILE *f)
    {
        if (pos == BUF_SZ)
        {
            flush_out(f);
        }

        buf[pos++] = c;
    }

    void write_int(int x, FILE *f)
    {
        static char num_buf[100];

        if (x < 0)
        {
            write_char('-', f);
            x *= -1;
        }

        int len = 0;
        for (; x >= 10; x /= 10)
        {
            num_buf[len++] = (char)('0' + (x % 10));
        }

        write_char((char)('0' + x), f);
        while (len)
        {
            write_char(num_buf[--len], f);
        }
        write_char('\n', f);
    }
}
#pragma endregion

struct bridge_t
{
    int a, b, w;

    int other(int cur)
    {
        return (a == cur) ? b : a;
    }
};

using adj_t = vector<vector<bridge_t *>>;
using state_t = bitset<(int)1e5>;
using edge_t = vector<bridge_t>;

void query(int i, int w, adj_t &adj, state_t &visited, int &count)
{
    visited[i] = true;
    for (auto &next : adj[i])
    {
        if (visited[next->other(i)] || next->w < w)
        {
            continue;
        }

        // visited[next->other(i)] = true;
        query(next->other(i), w, adj, visited, count);
    }

    count++;
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("tiltai.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int v, e;
    cin >> v >> e;

    edge_t edge(e);
    adj_t adj(v);
    for (size_t i = 0; i < e; i++)
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].w;

        edge[i].a--;
        edge[i].b--;

        adj[edge[i].a].push_back(&edge[i]);
        adj[edge[i].b].push_back(&edge[i]);
    }

    int q;
    cin >> q;

    state_t visited;
    for (size_t i = 0; i < q; i++)
    {
        int type, index, x;
        cin >> type >> index >> x;
        index--;

        if (type == 1)
        {
            edge[index].w = x;
        }
        else
        {
            visited.reset();

            int count = 0;
            query(index, x, adj, visited, count);
            cout << count << '\n';
        }
    }

    return 0;
}

Compilation message

bridges.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
bridges.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      | 
bridges.cpp: In function 'int main()':
bridges.cpp:204:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  204 |     for (size_t i = 0; i < e; i++)
      |                        ~~^~~
bridges.cpp:219:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  219 |     for (size_t i = 0; i < q; i++)
      |                        ~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 67 ms 564 KB Output is correct
4 Correct 6 ms 448 KB Output is correct
5 Correct 9 ms 468 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 8 ms 472 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 5 ms 476 KB Output is correct
11 Correct 6 ms 472 KB Output is correct
12 Correct 6 ms 500 KB Output is correct
13 Correct 8 ms 468 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 6 ms 340 KB Output is correct
17 Correct 10 ms 340 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8652 KB Output is correct
2 Correct 89 ms 10372 KB Output is correct
3 Correct 88 ms 10392 KB Output is correct
4 Correct 236 ms 10400 KB Output is correct
5 Correct 244 ms 10508 KB Output is correct
6 Execution timed out 3061 ms 9268 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 4932 KB Output is correct
2 Correct 2586 ms 2820 KB Output is correct
3 Execution timed out 3083 ms 4084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 9400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8652 KB Output is correct
2 Correct 89 ms 10372 KB Output is correct
3 Correct 88 ms 10392 KB Output is correct
4 Correct 236 ms 10400 KB Output is correct
5 Correct 244 ms 10508 KB Output is correct
6 Execution timed out 3061 ms 9268 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 67 ms 564 KB Output is correct
4 Correct 6 ms 448 KB Output is correct
5 Correct 9 ms 468 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 8 ms 472 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 5 ms 476 KB Output is correct
11 Correct 6 ms 472 KB Output is correct
12 Correct 6 ms 500 KB Output is correct
13 Correct 8 ms 468 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 8 ms 504 KB Output is correct
16 Correct 6 ms 340 KB Output is correct
17 Correct 10 ms 340 KB Output is correct
18 Correct 86 ms 8652 KB Output is correct
19 Correct 89 ms 10372 KB Output is correct
20 Correct 88 ms 10392 KB Output is correct
21 Correct 236 ms 10400 KB Output is correct
22 Correct 244 ms 10508 KB Output is correct
23 Execution timed out 3061 ms 9268 KB Time limit exceeded
24 Halted 0 ms 0 KB -