Submission #884032

#	Time	Username	Problem	Language	Result	Execution time	Memory
884032		fanwen	Tourism (JOI23_tourism)	C++17	28 / 100	5086 ms	18452 KiB

tourism

#include <bits/stdc++.h>

#define fi first
#define se second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

#ifdef LOCAL
    #include "debug.h"
#else
    #define clog if(false) cerr
#endif

const int MAX = 1e5 + 5;

int n, m, q, pos[MAX], ans[MAX], time_in[MAX], time_out[MAX], depth[MAX], anc[MAX][20];
vector <int> adj[MAX];

bool is_par(int u, int v) {
    return time_in[u] <= time_in[v] and time_in[v] <= time_out[u];
}

void dfs(int u, int p) {
    static int run = 0;
    time_in[u] = ++run;
    depth[u] = depth[p] + 1;
    anc[u][0] = p;
    for (int i = 1; i <= 17; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto v : adj[u]) if(v != p) {
        dfs(v, u);
    }
    time_out[u] = run;
}

int lca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    for (int i = 17; i >= 0; --i) if(depth[anc[u][i]] >= depth[v]) {
        u = anc[u][i];
    }

    if(u == v) return u;

    for (int i= 17; i >= 0; --i) if(anc[u][i] != anc[v][i]) {
        u = anc[u][i];
        v = anc[v][i];
    }
    return anc[u][0];
}

int solve(int l, int r) {
    int ans = 0;
    vector <int> p;
    for (int i = l; i <= r; ++i) {
        p.push_back(pos[i]);
    }
    sort(p.begin(), p.end(), [&] (const int &x, const int &y) {
         return time_in[x] < time_in[y];
    });
    int sz = (int) p.size();
    for (int i = 0; i < sz - 1; ++i) {
        p.push_back(lca(p[i], p[i + 1]));
    }
    sort(p.begin(), p.end(), [&] (const int &x, const int &y) {
         return time_in[x] < time_in[y];
    });
    p.erase(unique(p.begin(), p.end()), p.end());
    stack <int> st;
    for (int i = 0; i < (int) p.size(); ++i) {
        while(!st.empty() && !is_par(st.top(), p[i])) st.pop();
        if(!st.empty()) ans += depth[p[i]] - depth[st.top()];
        else ans++;
        st.push(p[i]);
    }
    return ans;
}

void you_make_it(void) {
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= m; ++i) cin >> pos[i];
    dfs(1, 0);
    for (int i = 0; i < q; ++i) {
        int l, r; cin >> l >> r;
        cout << solve(l, r) << '\n';
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("tourism");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:99:5: note: in expansion of macro 'file'
   99 |     file("tourism");
      |     ^~~~
tourism.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:99:5: note: in expansion of macro 'file'
   99 |     file("tourism");
      |     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41