oj.uz

Submission #1113833

# Submission time Handle Problem Language Result Execution time Memory
1113833 2024-11-17T14:34:10 Z MateiKing80 Inside information (BOI21_servers) C++14
50 / 100
 369 ms 38716 KB 
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()

const int N = 120000;
int n, q;

struct AIB
{
    int aib[2 * N + 5];
    vector<int> descos;
    inline int lsb(int x) {return x & -x;}
    void update(int pos, int val)
    {
        while(pos < n + q)
            aib[pos] += val,
            descos.push_back(pos),
            pos += lsb(pos);
    }
    int query(int pos)
    {
        int ans = 0;
        while(pos)
            ans += aib[pos],
            pos -= lsb(pos);
        return ans;
    }
    void sterge()
    {
        for(auto i : descos)
            aib[i] = 0;
        descos.clear();
    }
} ds;

struct Query
{
    char type;
    int to, time;
};
vector<Query> qry[N + 5];
vector<pii> vec[N + 5];
int ans[2 * N + 5], sz[N + 5], muchtopapa[N + 5];
int crdcr[N + 5], papa[N + 5], papasubc[N + 5];
bool viz[N + 5], amdat[N + 5];

void dfssz(int nod, int papa)
{
    sz[nod] = 1;
    for(auto [i, j] : vec[nod])
        if(!viz[i] && i != papa)
            dfssz(i, nod), sz[nod] += sz[i];
}

int dfsCentroid(int nod, int szinit)
{
    for(auto [i, j] : vec[nod])
        if(!viz[i] && sz[i] < sz[nod] && 2 * sz[i] >= szinit)
            return dfsCentroid(i, szinit);
    return nod;
}

void dfs(int nod, vector<int> &x)
{
    x.push_back(nod);
    amdat[nod] = true;
    for(auto [i, j] : vec[nod])
    {
        if(viz[i] || i == papa[nod])
            continue;
        papa[i] = nod;
        papasubc[i] = papasubc[nod];
        muchtopapa[i] = j;
        crdcr[i] = 0;
        if(j < muchtopapa[nod] && (crdcr[nod] & 1))
            crdcr[i] ++;
        if(j > muchtopapa[nod] && (crdcr[nod] & 2))
            crdcr[i] += 2;
        dfs(i, x);
    }
}

//crdcr[nod] & 1 => crescator de la nod in sus
//crdcr[nod] & 2 => descrescator de la nod in sus

void doCentroid(int nod)
{
    dfssz(nod, 0);
    int centr = dfsCentroid(nod, sz[nod]);
    vector<pair<int, vector<int>>> subarb;
    for(auto [i, j] : vec[centr])
    {
        if(viz[i])
            continue;
        subarb.push_back({i, {}});
        papa[i] = centr;
        papasubc[i] = i;
        muchtopapa[i] = j;
        crdcr[i] = 3;
        dfs(i, subarb.back().sc);
    }
    muchtopapa[centr] = 0;
    sort(all(subarb), [&](pair<int, vector<int>> a, pair<int, vector<int>> b)
    {
        return muchtopapa[a.fr] < muchtopapa[b.fr];
    });
    amdat[centr] = true;
    crdcr[centr] = 3;
    ds.update(1, 1);
    for(auto [i, v] : subarb)
    {
        for(auto j : v)
            for(auto k : qry[j])
            {
                if(k.type == 'c')
                {
                    //cout << centr << " " << j << " " << k.to << '\n';
                    if(muchtopapa[papasubc[j]] <= k.time && (crdcr[j] & 1))
                        ans[k.time] += ds.query(k.time);
                }
                else
                {
                    //cout << centr << " " << j << " " << k.to << " " << k.time << '\n';
                    if(k.to != centr && amdat[k.to] && muchtopapa[papasubc[k.to]] > muchtopapa[papasubc[j]] &&
                       muchtopapa[k.to] <= k.time && (crdcr[k.to] & 2) && (crdcr[j] & 1))
                        ans[k.time] = -1;
                    else if(k.to == centr && (crdcr[j] & 1) && muchtopapa[papasubc[j]] <= k.time)
                        ans[k.time] = -1;

                }
            }
        for(auto j : v)
            if(crdcr[j] & 2)
                ds.update(muchtopapa[j], 1);
    }
    ds.update(1, -1);
    for(auto i : qry[centr])
    {
        if(i.type == 'c')
            ans[i.time] += ds.query(i.time);
        else
        {
            //cout << centr << " " << centr << " " << i.to << " " << i.time << '\n';
            if(amdat[i.to] && (crdcr[i.to] & 2) && muchtopapa[i.to] <= i.time)
                ans[i.time] = -1;
        }
    }
    ds.sterge();
    amdat[centr] = false;
    for(auto i : subarb)
        for(auto j : i.sc)
            amdat[j] = false;
    viz[centr] = true;
    for(auto [i, j] : vec[centr])
        if(!viz[i])
            doCentroid(i);
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i < n + q; i ++)
    {
        char t;
        cin >> t;
        if(t == 'S')
        {
            int u, v;
            cin >> u >> v;
            vec[u].push_back({v, i});
            vec[v].push_back({u, i});
            ans[i] = -69;
        }
        if(t == 'Q')
        {
            int u, v;
            cin >> u >> v;
            qry[v].push_back({'q', u, i});
            ans[i] = -2;
        }
        if(t == 'C')
        {
            int u;
            cin >> u;
            qry[u].push_back({'c', 0, i});
        }
    }
    doCentroid(1);
    for(int i = 1; i < n + q; i ++)
    {
        if(ans[i] == -1)
            cout << "yes\n";
        else if(ans[i] == -2)
            cout << "no\n";
        else if(ans[i] >= 0)
            cout << ans[i] + 1 << '\n';
    }
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
*/

Compilation message

servers.cpp: In function 'void dfssz(int, int)':
servers.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'int dfsCentroid(int, int)':
servers.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'void dfs(int, std::vector<int>&)':
servers.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'void doCentroid(int)':
servers.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for(auto [i, j] : vec[centr])
      |              ^
servers.cpp:115:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |     for(auto [i, v] : subarb)
      |              ^
servers.cpp:159:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  159 |     for(auto [i, j] : vec[centr])
      |              ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12456 KB Output is correct
2 Correct 57 ms 14040 KB Output is correct
3 Correct 51 ms 13960 KB Output is correct
4 Correct 55 ms 14156 KB Output is correct
5 Correct 56 ms 14152 KB Output is correct
6 Correct 52 ms 14148 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12456 KB Output is correct
2 Correct 57 ms 14040 KB Output is correct
3 Correct 51 ms 13960 KB Output is correct
4 Correct 55 ms 14156 KB Output is correct
5 Correct 56 ms 14152 KB Output is correct
6 Correct 52 ms 14148 KB Output is correct
7 Incorrect 35 ms 13136 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12376 KB Output is correct
2 Correct 263 ms 38576 KB Output is correct
3 Correct 295 ms 38712 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12376 KB Output is correct
2 Correct 263 ms 38576 KB Output is correct
3 Correct 295 ms 38712 KB Output is correct
4 Incorrect 38 ms 13136 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12368 KB Output is correct
2 Correct 356 ms 30636 KB Output is correct
3 Correct 328 ms 30728 KB Output is correct
4 Correct 258 ms 35860 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12368 KB Output is correct
2 Correct 356 ms 30636 KB Output is correct
3 Correct 328 ms 30728 KB Output is correct
4 Correct 258 ms 35860 KB Output is correct
5 Incorrect 36 ms 13012 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12368 KB Output is correct
2 Correct 245 ms 24332 KB Output is correct
3 Correct 248 ms 22224 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12368 KB Output is correct
2 Correct 245 ms 24332 KB Output is correct
3 Correct 248 ms 22224 KB Output is correct
4 Incorrect 36 ms 13128 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12412 KB Output is correct
2 Correct 332 ms 30780 KB Output is correct
3 Correct 349 ms 30660 KB Output is correct
4 Correct 250 ms 35856 KB Output is correct
5 Correct 36 ms 13392 KB Output is correct
6 Correct 259 ms 24332 KB Output is correct
7 Correct 279 ms 22200 KB Output is correct
8 Correct 273 ms 22788 KB Output is correct
9 Correct 262 ms 22880 KB Output is correct
10 Correct 277 ms 27212 KB Output is correct
11 Correct 273 ms 25652 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12412 KB Output is correct
2 Correct 332 ms 30780 KB Output is correct
3 Correct 349 ms 30660 KB Output is correct
4 Correct 250 ms 35856 KB Output is correct
5 Correct 36 ms 13392 KB Output is correct
6 Correct 259 ms 24332 KB Output is correct
7 Correct 279 ms 22200 KB Output is correct
8 Correct 273 ms 22788 KB Output is correct
9 Correct 262 ms 22880 KB Output is correct
10 Correct 277 ms 27212 KB Output is correct
11 Correct 273 ms 25652 KB Output is correct
12 Incorrect 38 ms 13128 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12456 KB Output is correct
2 Correct 61 ms 14232 KB Output is correct
3 Correct 68 ms 14152 KB Output is correct
4 Correct 64 ms 14312 KB Output is correct
5 Correct 60 ms 14160 KB Output is correct
6 Correct 63 ms 14148 KB Output is correct
7 Correct 38 ms 13196 KB Output is correct
8 Correct 276 ms 38716 KB Output is correct
9 Correct 267 ms 38612 KB Output is correct
10 Correct 38 ms 13384 KB Output is correct
11 Correct 362 ms 30752 KB Output is correct
12 Correct 323 ms 30604 KB Output is correct
13 Correct 236 ms 35856 KB Output is correct
14 Correct 40 ms 13392 KB Output is correct
15 Correct 233 ms 24348 KB Output is correct
16 Correct 286 ms 22200 KB Output is correct
17 Correct 277 ms 22676 KB Output is correct
18 Correct 277 ms 22856 KB Output is correct
19 Correct 279 ms 27200 KB Output is correct
20 Correct 286 ms 25636 KB Output is correct
21 Correct 289 ms 33328 KB Output is correct
22 Correct 277 ms 32284 KB Output is correct
23 Correct 263 ms 22800 KB Output is correct
24 Correct 272 ms 22964 KB Output is correct
25 Correct 369 ms 33496 KB Output is correct
26 Correct 254 ms 21568 KB Output is correct
27 Correct 263 ms 21556 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12456 KB Output is correct
2 Correct 61 ms 14232 KB Output is correct
3 Correct 68 ms 14152 KB Output is correct
4 Correct 64 ms 14312 KB Output is correct
5 Correct 60 ms 14160 KB Output is correct
6 Correct 63 ms 14148 KB Output is correct
7 Correct 38 ms 13196 KB Output is correct
8 Correct 276 ms 38716 KB Output is correct
9 Correct 267 ms 38612 KB Output is correct
10 Correct 38 ms 13384 KB Output is correct
11 Correct 362 ms 30752 KB Output is correct
12 Correct 323 ms 30604 KB Output is correct
13 Correct 236 ms 35856 KB Output is correct
14 Correct 40 ms 13392 KB Output is correct
15 Correct 233 ms 24348 KB Output is correct
16 Correct 286 ms 22200 KB Output is correct
17 Correct 277 ms 22676 KB Output is correct
18 Correct 277 ms 22856 KB Output is correct
19 Correct 279 ms 27200 KB Output is correct
20 Correct 286 ms 25636 KB Output is correct
21 Correct 289 ms 33328 KB Output is correct
22 Correct 277 ms 32284 KB Output is correct
23 Correct 263 ms 22800 KB Output is correct
24 Correct 272 ms 22964 KB Output is correct
25 Correct 369 ms 33496 KB Output is correct
26 Correct 254 ms 21568 KB Output is correct
27 Correct 263 ms 21556 KB Output is correct
28 Incorrect 37 ms 13128 KB Extra information in the output file
29 Halted 0 ms 0 KB -