oj.uz

답안 #850700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850700 2023-09-17T09:52:03 Z danikoynov Tourism (JOI23_tourism) C++14
52 / 100
 5000 ms 42236 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;

struct query
{
    int l, r, idx;
} task[maxn];

int n, m, c[maxn], q;
vector < int > adj[maxn];

void input()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    for (int i = 1; i <= m; i ++)
    {
        cin >> c[i];
    }

    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].l >> task[i].r;
        task[i].idx = i;
    }
}


int depth[maxn], tin[maxn], tout[maxn];
int occ[2 * maxn], rev[2 * maxn], timer;
int sub[maxn], heavy[maxn];

void euler(int v = 1, int p = - 1)
{
    occ[++ timer] = v;
    tin[v] = timer;
    rev[timer] = v;
    sub[v] = 1;
    heavy[v] = -1;
    for (int u : adj[v])
    {
        if (u == p)
            continue;
        depth[u] = depth[v] + 1;
        euler(u, v);
        if (heavy[v] == -1 || sub[u] > sub[heavy[v]])
            heavy[v] = u;
        sub[v] += sub[u];
        occ[++ timer] = v;
    }
    tout[v] = timer;
}

const int maxlog = 20;

int lg[2 * maxn], dp[maxlog][2 * maxn];

void sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = occ[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j); i ++)
        {
            dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
            if (depth[dp[j - 1][i]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i];
        }
}

int get_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1;
    int lca = dp[len][r - (1 << len) + 1];
    if (depth[dp[len][l]] < depth[lca])
        lca = dp[len][l];
    return lca;
}

int get_distance(int v, int u)
{
    return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}

struct interval
{
    int left, right, value;

    interval(int _left = 0, int _right = 0, int _value = 0)
    {
        left = _left;
        right = _right;
        value = _value;
    }
    bool operator < (const interval seg) const
    {
        if (left == seg.left)
        {

            /// values cannot be the same
            return value > seg.value;

        }
        else
            return left < seg.left;
    }
};
struct chain
{
    int top, left, right;


    set < interval > act;
} st[maxn];

int ch_idx[maxn], ch_cnt, ord[maxn], last, ch_pos[maxn];

void hld(int v = 1, int p = -1)
{
    ///cout << v << " : " << p << endl;
    ch_idx[v] = ch_cnt;
    ord[++ last] = v;
    ch_pos[v] = last;
    st[ch_idx[v]].right = last;
    if (heavy[v] != -1)
        hld(heavy[v], v);
    for (int u : adj[v])
    {
        if (u == p || u == heavy[v])
            continue;
        ch_cnt ++;
        st[ch_cnt].top = v;
        st[ch_cnt].left = last + 1;
        st[ch_cnt].right = last + 1;
        hld(u, v);
    }
}

void decompose()
{
    ch_idx[1] = 1;
    ch_cnt = 1;
    ch_pos[1] = 1;
    st[ch_cnt].left = st[ch_cnt].right = 1;
    st[ch_cnt].top = 0;
    hld();

    /**cout << ch_cnt << endl;
    for (int i = 1; i <= ch_cnt; i ++)
        cout << st[i].left << " " << st[i].right << endl;
    for (int i = 1; i <= n; i ++)
    cout << ord[i] << " ";
    cout << endl;*/
}

int fen[maxn];

void update(int v, int val)
{
    for (int i = v; i <= m; i += (i & -i))
        fen[i] += val;
}

int query_sum(int v)
{
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

int col[maxn];
void write_on_chain(int idx, int left, int right, int val)
{
    for (int i = left; i <= right; i ++)
    {
        if (col[i] != 0)
            update(col[i], - 1);
        col[i] = val;
    }
    update(val, right - left + 1);
    return;
    interval seg(left, right, val);


    st[idx].act.insert(seg);
    set < interval > :: iterator it, bef, aft;
    it = st[idx].act.find(seg);
    update(val, right - left + 1);
    ///cout << "write on chain " << val << " " << left << " " << right << endl;
    if (it != st[idx].act.begin())
    {
        bef = prev(it);

        if (bef -> left <= left && bef -> right >= right)
        {
            update(bef -> value, - (right - left + 1));
            interval lf_split(bef -> left, left - 1, bef -> value);
            interval rf_split(right + 1, bef -> right, bef -> value);
            st[idx].act.erase(bef);
            if (lf_split.left <= lf_split.right)
                st[idx].act.insert(lf_split);
            if (rf_split.left <= rf_split.right)
                st[idx].act.insert(rf_split);
        }
        else if (bef -> right >= left)
        {

            update(bef -> value, - (bef -> right - left + 1));

            interval new_bef(bef -> left, left - 1, bef -> value);
            st[idx].act.erase(bef);
            if (new_bef.left <= new_bef.right)
                st[idx].act.insert(new_bef);
        }
    }

    it = st[idx].act.find(seg);
    if (next(it) != st[idx].act.end())
    {
        aft = next(it);
        if (aft -> right <= right)
        {
            update(aft -> value, - (aft -> right - aft -> left + 1));
            st[idx].act.erase(aft);
        }
        else if (aft -> left <= right)
        {
            update(aft -> value, - (right - aft -> left + 1));
            interval new_aft(right + 1, aft -> right, aft -> value);
            st[idx].act.erase(aft);
            if (new_aft.left <= new_aft.right)
                st[idx].act.insert(new_aft);
        }
    }



}

void write_on_path(int v, int p, int val)
{
    ///cout << "write on path " << v << " " << p << endl;
    while(ch_idx[v] != ch_idx[p])
    {
        write_on_chain(ch_idx[v], st[ch_idx[v]].left, ch_pos[v], val);
        v = st[ch_idx[v]].top;
    }


        if (ch_pos[p] < ch_pos[v])
            write_on_chain(ch_idx[v], ch_pos[p] + 1, ch_pos[v], val);

}


vector < query > ask[maxn];
int res[maxn];
void queries()
{

    ///q = 1;
       for (int i = 1; i <= q; i ++)
        ask[task[i].l].push_back(task[i]);

       for (int i = m; i > 0; i --)
       {
           if (i != m)
           {
               int v = c[i], u = c[i + 1];
               int lca = get_lca(v, u);
               write_on_path(v, lca, i);
               write_on_path(u, lca, i);
           }
            /**cout << "step " << i << endl;
            for (int j = 1; j <= m; j ++)
                cout << query_sum(j) - query_sum(j - 1) << " ";
            cout << endl;*/
           for (query cur : ask[i])
           {
               res[cur.idx] = query_sum(cur.r - 1) + 1;
           }
       }


       for (int i = 1; i <= q; i ++)
        cout << res[i] << endl;
}

void solve()
{
    input();
    euler();
    sparse_table();
    decompose();
    queries();

}

int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 4 ms 23132 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23132 KB Output is correct
7 Correct 4 ms 23132 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct
9 Correct 4 ms 23132 KB Output is correct
10 Correct 4 ms 23260 KB Output is correct
11 Correct 4 ms 23356 KB Output is correct
12 Correct 4 ms 23384 KB Output is correct
13 Correct 4 ms 23132 KB Output is correct
14 Correct 4 ms 23132 KB Output is correct
15 Correct 4 ms 23256 KB Output is correct
16 Correct 4 ms 23248 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23132 KB Output is correct
19 Correct 4 ms 23132 KB Output is correct
20 Correct 4 ms 23132 KB Output is correct
21 Correct 4 ms 23132 KB Output is correct
22 Correct 4 ms 23356 KB Output is correct
23 Correct 5 ms 23132 KB Output is correct
24 Correct 4 ms 23352 KB Output is correct
25 Correct 4 ms 23256 KB Output is correct
26 Correct 4 ms 23132 KB Output is correct
27 Correct 3 ms 16984 KB Output is correct
28 Correct 4 ms 23132 KB Output is correct
29 Correct 4 ms 23132 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 4 ms 23132 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23132 KB Output is correct
7 Correct 4 ms 23132 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct
9 Correct 4 ms 23132 KB Output is correct
10 Correct 4 ms 23260 KB Output is correct
11 Correct 4 ms 23356 KB Output is correct
12 Correct 4 ms 23384 KB Output is correct
13 Correct 4 ms 23132 KB Output is correct
14 Correct 4 ms 23132 KB Output is correct
15 Correct 4 ms 23256 KB Output is correct
16 Correct 4 ms 23248 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23132 KB Output is correct
19 Correct 4 ms 23132 KB Output is correct
20 Correct 4 ms 23132 KB Output is correct
21 Correct 4 ms 23132 KB Output is correct
22 Correct 4 ms 23356 KB Output is correct
23 Correct 5 ms 23132 KB Output is correct
24 Correct 4 ms 23352 KB Output is correct
25 Correct 4 ms 23256 KB Output is correct
26 Correct 4 ms 23132 KB Output is correct
27 Correct 3 ms 16984 KB Output is correct
28 Correct 4 ms 23132 KB Output is correct
29 Correct 4 ms 23132 KB Output is correct
30 Correct 5 ms 25436 KB Output is correct
31 Correct 6 ms 25524 KB Output is correct
32 Correct 7 ms 25516 KB Output is correct
33 Correct 6 ms 25436 KB Output is correct
34 Correct 6 ms 25436 KB Output is correct
35 Correct 5 ms 25436 KB Output is correct
36 Correct 6 ms 25436 KB Output is correct
37 Correct 6 ms 25436 KB Output is correct
38 Correct 12 ms 25672 KB Output is correct
39 Correct 11 ms 25676 KB Output is correct
40 Correct 11 ms 25692 KB Output is correct
41 Correct 11 ms 25692 KB Output is correct
42 Correct 11 ms 25692 KB Output is correct
43 Correct 11 ms 25656 KB Output is correct
44 Correct 8 ms 25436 KB Output is correct
45 Correct 7 ms 25436 KB Output is correct
46 Correct 8 ms 25632 KB Output is correct
47 Correct 9 ms 25436 KB Output is correct
48 Correct 8 ms 25436 KB Output is correct
49 Correct 8 ms 25436 KB Output is correct
50 Correct 5 ms 25436 KB Output is correct
51 Correct 5 ms 25436 KB Output is correct
52 Correct 5 ms 25432 KB Output is correct
53 Correct 5 ms 25520 KB Output is correct
54 Correct 5 ms 25432 KB Output is correct
55 Correct 6 ms 25436 KB Output is correct
56 Correct 3 ms 17244 KB Output is correct
57 Correct 5 ms 25436 KB Output is correct
58 Correct 7 ms 25436 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 17244 KB Output is correct
4 Execution timed out 5082 ms 39452 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 57 ms 32812 KB Output is correct
3 Correct 79 ms 33140 KB Output is correct
4 Correct 73 ms 33500 KB Output is correct
5 Correct 113 ms 35360 KB Output is correct
6 Correct 107 ms 35156 KB Output is correct
7 Correct 116 ms 35360 KB Output is correct
8 Correct 112 ms 35152 KB Output is correct
9 Correct 126 ms 35456 KB Output is correct
10 Correct 108 ms 35328 KB Output is correct
11 Correct 104 ms 35416 KB Output is correct
12 Correct 116 ms 35504 KB Output is correct
13 Correct 113 ms 35924 KB Output is correct
14 Correct 120 ms 36720 KB Output is correct
15 Correct 132 ms 40208 KB Output is correct
16 Correct 120 ms 35840 KB Output is correct
17 Correct 120 ms 35944 KB Output is correct
18 Correct 120 ms 35832 KB Output is correct
19 Correct 787 ms 35480 KB Output is correct
20 Correct 853 ms 35396 KB Output is correct
21 Correct 755 ms 35404 KB Output is correct
22 Correct 733 ms 35396 KB Output is correct
23 Correct 832 ms 35396 KB Output is correct
24 Correct 803 ms 35392 KB Output is correct
25 Correct 825 ms 35412 KB Output is correct
26 Correct 768 ms 35436 KB Output is correct
27 Correct 799 ms 35432 KB Output is correct
28 Correct 745 ms 35408 KB Output is correct
29 Correct 812 ms 35668 KB Output is correct
30 Correct 780 ms 35660 KB Output is correct
31 Correct 731 ms 35920 KB Output is correct
32 Correct 778 ms 36532 KB Output is correct
33 Correct 691 ms 37800 KB Output is correct
34 Correct 921 ms 40228 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 17240 KB Output is correct
4 Correct 128 ms 36660 KB Output is correct
5 Correct 119 ms 36688 KB Output is correct
6 Correct 143 ms 38304 KB Output is correct
7 Correct 149 ms 42132 KB Output is correct
8 Correct 151 ms 42120 KB Output is correct
9 Correct 165 ms 42236 KB Output is correct
10 Correct 149 ms 42148 KB Output is correct
11 Correct 147 ms 42064 KB Output is correct
12 Correct 154 ms 42068 KB Output is correct
13 Correct 150 ms 42064 KB Output is correct
14 Correct 31 ms 22364 KB Output is correct

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 4 ms 23132 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23132 KB Output is correct
7 Correct 4 ms 23132 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct
9 Correct 4 ms 23132 KB Output is correct
10 Correct 4 ms 23260 KB Output is correct
11 Correct 4 ms 23356 KB Output is correct
12 Correct 4 ms 23384 KB Output is correct
13 Correct 4 ms 23132 KB Output is correct
14 Correct 4 ms 23132 KB Output is correct
15 Correct 4 ms 23256 KB Output is correct
16 Correct 4 ms 23248 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23132 KB Output is correct
19 Correct 4 ms 23132 KB Output is correct
20 Correct 4 ms 23132 KB Output is correct
21 Correct 4 ms 23132 KB Output is correct
22 Correct 4 ms 23356 KB Output is correct
23 Correct 5 ms 23132 KB Output is correct
24 Correct 4 ms 23352 KB Output is correct
25 Correct 4 ms 23256 KB Output is correct
26 Correct 4 ms 23132 KB Output is correct
27 Correct 3 ms 16984 KB Output is correct
28 Correct 4 ms 23132 KB Output is correct
29 Correct 4 ms 23132 KB Output is correct
30 Correct 5 ms 25436 KB Output is correct
31 Correct 6 ms 25524 KB Output is correct
32 Correct 7 ms 25516 KB Output is correct
33 Correct 6 ms 25436 KB Output is correct
34 Correct 6 ms 25436 KB Output is correct
35 Correct 5 ms 25436 KB Output is correct
36 Correct 6 ms 25436 KB Output is correct
37 Correct 6 ms 25436 KB Output is correct
38 Correct 12 ms 25672 KB Output is correct
39 Correct 11 ms 25676 KB Output is correct
40 Correct 11 ms 25692 KB Output is correct
41 Correct 11 ms 25692 KB Output is correct
42 Correct 11 ms 25692 KB Output is correct
43 Correct 11 ms 25656 KB Output is correct
44 Correct 8 ms 25436 KB Output is correct
45 Correct 7 ms 25436 KB Output is correct
46 Correct 8 ms 25632 KB Output is correct
47 Correct 9 ms 25436 KB Output is correct
48 Correct 8 ms 25436 KB Output is correct
49 Correct 8 ms 25436 KB Output is correct
50 Correct 5 ms 25436 KB Output is correct
51 Correct 5 ms 25436 KB Output is correct
52 Correct 5 ms 25432 KB Output is correct
53 Correct 5 ms 25520 KB Output is correct
54 Correct 5 ms 25432 KB Output is correct
55 Correct 6 ms 25436 KB Output is correct
56 Correct 3 ms 17244 KB Output is correct
57 Correct 5 ms 25436 KB Output is correct
58 Correct 7 ms 25436 KB Output is correct
59 Correct 3 ms 19036 KB Output is correct
60 Correct 3 ms 16988 KB Output is correct
61 Correct 4 ms 17244 KB Output is correct
62 Execution timed out 5082 ms 39452 KB Time limit exceeded
63 Halted 0 ms 0 KB -