Submission #1290075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290075		quangminh412	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	1607 ms	136976 KiB

sightseeing

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "TINHCLDD";

void solve();
signed main()
{
    if (fopen((name + ".INP").c_str(), "r"))
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int oo = 0x3f3f3f3f;
const int maxn = 5e5 + 1;

vector<pair<int, int>> save[maxn];
vector<array<int, 3>> edges;
vector<int> cmp[maxn];
int tp[maxn], pos[maxn];
int n, m, q;

void merge(int u, int v, int w)
{
    int tpU = tp[u], tpV = tp[v];
    if (tpU == tpV)
    {
        if (pos[1] == tpU)
            save[tpU].push_back({(int)cmp[tpU].size() - 1, w});
        return;
    }
    if ((int)cmp[tpU].size() > (int)cmp[tpV].size())
    {
        swap(tpU, tpV);
        swap(u, v);
    }
    tp[u] = tp[v];
    for (int x : cmp[tpU])
    {
        tp[x] = tpV;
        pos[x] = tpV;
        cmp[tpV].push_back(x);
    }
    if (pos[1] == tpV)
        save[tpV].push_back({(int)cmp[tpV].size() - 1, w});
}

void solve()
{
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++)
    {
        int x, y, z; cin >> x >> y >> z;
        edges.push_back({z, x, y});
    }

    sort(edges.begin(), edges.end(), greater<array<int, 3>>());
    for (int i = 1; i <= n; i++)
    {
        tp[i] = pos[i] = i;
        cmp[i].push_back(i);
    }
    for (array<int, 3> it : edges)
    {
        int u = it[1], v = it[2], w = it[0];
        merge(u, v, w);
    }

    vector<int> res(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        int inf = -oo, N = (int)save[i].size(), pos = N - 1, M = (int)cmp[i].size();
        for (int j = M - 1; j >= 0; j--)
        {
            int u = cmp[i][j];
            while (pos >= 0 && save[i][pos].first >= j)
            {
                inf = max(inf, save[i][pos].second);
                pos--;
            }
            res[u] = max(res[u], inf);
        }
    }

    while (q--)
    {
        int u; cin >> u;

        cout << res[u] << '\n';
    }
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10