QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#418959#8716. 树paoxiaomo#WA 0ms7700kbC++206.5kb2024-05-23 16:40:582024-05-23 16:40:58

Judging History

你现在查看的是最新测评结果

  • [2024-05-23 16:40:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7700kb
  • [2024-05-23 16:40:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define pb push_back
#define LNF 1e18
#define INF 0x7fffffff
#define int long long
#define lowbit(x) ((x) & (-x))
#define abs(x) llabs(x)
#define endl '\n'
#define Y() cout << "Yes" << endl
#define N() cout << "No" << endl
const db eps = 1e-9;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
vector<int> pth[200005];
int b[200005], add[200005], f[200005];
struct RMQ
{ // 求序列中区间最大?最小值的下标
    int n;
    vector<int> lg, nu;
    vector<array<int, 25>> dp; // 固定内部数组降低常数
    int get(const int &a, const int &b)
    {
        return nu[a] < nu[b] ? a : b; // 自定义比较函数,返回在原数组中较大的下标
    }
    RMQ() {}
    RMQ(vector<int> &v)
    { // v的有效下标从1开始,v.size()-1结束
        n = v.size() - 1;
        nu = v;
        lg.resize(n + 1);
        dp.resize(n + 1);
        lg[1] = 0;
        for (int i = 2; i <= n; i++)
        {
            lg[i] = lg[i >> 1] + 1;
        }
        for (int i = 1; i <= n; i++)
        {
            dp[i][0] = i;
        }
        for (int j = 1; j <= lg[n]; j++)
        {
            for (int i = 1; i <= n - (1 << j) + 1; i++)
            {
                dp[i][j] = get(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int getidex(const int &l, const int &r) // 返回最值下标
    {
        int len = lg[r - l + 1];
        return get(dp[l][len], dp[r - (1 << len) + 1][len]);
    }
    int getnum(const int &l, const int &r) // 返回最值
    {
        return nu[getidex(l, r)];
    }
};
struct GRAPH
{
    vector<vector<pair<int, int>>> pth;
    vector<int> dep, first, nu, ref;
    int cnt = 0;
    GRAPH(int n)
    {
        pth.resize(n + 1);
        dep.resize(n + 1);
        first.resize(n + 1);
        nu.resize(n * 2 + 1);
        ref.resize(n * 2 + 1);
        cnt = 0; // 构造好了以后直接加边
    }
    void add_edge(int u, int v, int w = 1)
    { // 加双向边
        pth[u].push_back({v, w});
        pth[v].push_back({u, w});
    }
    void dfs(int pos, int fa)
    {
        first[pos] = ++cnt; // 第一次碰到这个点的dfs序
        nu[cnt] = dep[pos]; // 这个dfs序的深度
        ref[cnt] = pos;
        for (auto [to, len] : pth[pos])
        {
            if (to == fa)
                continue;
            dep[to] = dep[pos] + len; // 当前点深度
            dfs(to, pos);
            nu[++cnt] = dep[pos];
            ref[cnt] = pos;
        }
    };
    RMQ rmq;
    void prepare(int st)
    { // st是树的根节点
        dfs(st, 0);
        rmq = RMQ(nu);
    }
    int query_lca(int x, int y)
    { // 询问两点间的最近公共祖先
        int l, r;
        l = first[x], r = first[y];
        if (l > r)
            swap(l, r);
        int t = rmq.getidex(l, r);
        int lca = ref[t];
        return lca;
    };
    int query_dis(int x, int y)
    { // 询问两点间的距离
        int len = dep[x] + dep[y] - 2 * dep[query_lca(x, y)];
        return len;
    };
};
void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    GRAPH g(n + 1);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g.add_edge(u, v);
    }
    g.prepare(1);
    int ans = 2, fore = 0, flag = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
    }
    auto cal = [&](int i) -> void
    {
        if (i == 2)
        {
            int lc = g.query_lca(b[2], b[1]);
            if (lc == b[2])
            {
                fore = 1;
            }
            else
            {
                fore = -1;
            }
            return;
        }
        f[i] = fore;
        int lca = g.query_lca(b[i], b[i - 1]);
        // cout << lca << endl;
        // cout << fore << " ";
        if (lca == b[i] || lca == b[i - 1])
        {
            // cout << i << endl;
            if (g.dep[b[i]] > g.dep[b[i - 1]])
            {
                flag = -1;
            }
            else
            {
                flag = 1;
            }
            if (fore != flag)
                ans++, add[i]++;
            fore = flag;

            // cout << ans << endl;
        }
        else
        {
            ans++, add[i]++;
            flag = 1;
            fore = -1;
        }
    };
    auto cal1 = [&](int i) -> void
    {
        if (i == 2)
        {
            int lc = g.query_lca(b[2], b[1]);
            if (lc == b[2])
            {
                fore = 1;
            }
            else
            {
                fore = -1;
            }
            f[i + 1] = fore;
            return;
        }
        add[i] = 0;
        fore = f[i];
        int lca = g.query_lca(b[i], b[i - 1]);
        // cout << lca << endl;
        // cout << fore << " ";
        if (lca == b[i] || lca == b[i - 1])
        {
            // cout << i << endl;
            if (g.dep[b[i]] > g.dep[b[i - 1]])
            {
                flag = -1;
            }
            else
            {
                flag = 1;
            }
            if (fore != flag)
                ans++, add[i]++;
            fore = flag;

            // cout << ans << endl;
        }
        else
        {
            ans++, add[i]++;
            flag = 1;
            fore = -1;
        }
        f[i + 1] = fore;
    };

    for (int i = 2; i <= m; i++)
    {
        cal(i);
        cout << ans << endl;
    }
    // cout << endl;
    // f[m + 1] = fore;
    // if (f[m + 1] != 0)
    //     ans++;
    // for (int i = 1; i <= m; i++)
    //     cout << add[i] << " ";
    // cout << endl;
    // cout << ans << endl;
    while (q--)
    {
        int p, w;
        cin >> p >> w;
        if(m==1||m==2){
            cout<<m<<endl;continue;
        }
        ans -= (add[p] + add[p + 1] + add[p + 2]);
        // if (f[m + 1] != 0)
        //     ans--;
        b[p] = w;
        if (p != 1)
        {
            cal1(p);
        }
        if (p + 1 <= m)
            cal1(p + 1);
        if (p + 2 <= m)
            cal1(p + 2);
        cout << ans << endl;
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7700kb

input:

5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3

output:

2
3
4
4
4
4
5

result:

wrong answer 1st numbers differ - expected: '4', found: '2'