Submission #366044

#	Time	Username	Problem	Language	Result	Execution time	Memory
366044		idk321	Synchronization (JOI13_synchronization)	C++11	30 / 100	293 ms	13804 KiB

synchronization

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

const int N = 100005;
vector<int> adj[N];
array<int, 2> edge[N];




int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        edge[i] = {x, y};
    }

    vector<int> change(m);
    for (int i = 0; i < m; i++) cin >> change[i];
    bool exist[N] = {};


    set<array<int, 4>> s;
    for (int i = 1; i <= n; i++)
    {
        s.insert({i, i, i, i});
    }
    for (int i = 0; i < m; i++)
    {
        int e = change[i];
        int a = edge[e][0];
        int b = edge[e][1];
        if (exist[e])
        {
            auto it = s.upper_bound({b, N, N, N});
            it--;
            auto cur = *it;
            s.erase(it);
            s.insert({cur[0], a, cur[2], cur[3]});
            s.insert({b, cur[1], cur[2], cur[3]});

        } else
        {
            auto it1 = s.upper_bound({a, N, N, N});
            it1--;
            auto it2 = s.upper_bound({b, N, N, N});
            it2--;
            auto ar1 = *it1;
            auto ar2 = *it2;
            s.erase(it1);
            s.erase(it2);
            s.insert({ar1[0], ar2[1], min(ar1[2], ar2[2]), max(ar1[3], ar2[3])});
        }
        exist[e] = !exist[e];
    }

    for (int q1 = 0; q1 < q; q1++)
    {

        int c;
        cin >> c;
        auto it = s.upper_bound({c, N, N, N});
        it--;
        auto cur = *it;
        cout << (cur[3] - cur[2] + 1) << "\n";
    }
}

/*
6 7 6
1 2
2 3
3 4
4 5
5 6
1
1
1
3
2
2
4
1
2
3
4
5
6
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40