oj.uz

Submission #1036716

# Submission time Handle Problem Language Result Execution time Memory
1036716 2024-07-27T15:58:56 Z vjudge1 Inside information (BOI21_servers) C++17
52.5 / 100
 246 ms 88508 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn_s1 = 4007, mxn_full = 12e4+7;
ll n, q, cnt[mxn_s1], tl[mxn_full], h[mxn_full], up[mxn_full][20], mx[mxn_full][20], mn[mxn_full][20];
bool connected[mxn_full], lis[mxn_full][20], lds[mxn_full][20];
vector<vector<ll>> v(mxn_s1);
vector<vector<pair<ll,ll>>> g(mxn_full);
void dfs(ll u, ll v)
{
    for (pair<ll,ll> i : g[u])
    {
        if (i.fi != v)
        {
            h[i.fi] = h[u]+1; up[i.fi][0] = u; 
            mx[i.fi][0] = mn[i.fi][0] = i.se;
            lis[i.fi][0] = lds[i.fi][0] = 1;
            dfs(i.fi,u);
        }
    }
}
void build_lca()
{
    for (ll j = 1; j <= 19; j++)
    {
        for (ll i = 1; i <= n; i++) 
        {
            mx[i][j] = max(mx[i][j-1],mx[up[i][j-1]][j-1]);
            mn[i][j] = min(mn[i][j-1],mn[up[i][j-1]][j-1]);
            lis[i][j] = (lis[i][j-1] && lis[up[i][j-1]][j-1] && (mx[i][j-1] < mn[up[i][j-1]][j-1]));
            lds[i][j] = (lds[i][j-1] && lds[up[i][j-1]][j-1] && (mn[i][j-1] > mx[up[i][j-1]][j-1]));
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }
}
ll lift(ll a, ll b)
{
    for (ll i = 19; i >= 0; i--) if (b>>i&1) a = up[a][i];
    return a;
}
bool lis_ck(ll a, ll b)
{
    bool ck = 1; ll mxx = 0;
    for (ll i = 19; i >= 0; i--) if (b>>i&1) {ck &= (lis[a][i] && mn[a][i] > mxx); mxx = mx[a][i]; a = up[a][i];}
    return ck;
}
bool lds_ck(ll a, ll b)
{
    bool ck = 1; ll mnn = 1e18;
    for (ll i = 19; i >= 0; i--) if (b>>i&1) {ck &= (lds[a][i] && mx[a][i] < mnn); mnn = mn[a][i]; a = up[a][i];}
    return ck;
}
ll lca(ll a, ll b)
{
    if (h[a] != h[b])
    {
        if (h[a] < h[b]) swap(a,b);
        ll k = h[a]-h[b];
        for (ll i = __lg(k); i >= 0; i--)
        {
            if (k >> i & 1) a = up[a][i];
        }
    }
    if (a == b) return a;
    for (ll i = 19; i >= 0; i--) 
    {
        if (up[a][i] != up[b][i]) {a = up[a][i]; b = up[b][i];}
    }
    return up[a][0];
}
ll rmx(ll a, ll b)
{
    ll ans = 0;
    if (h[a] != h[b])
    {
        if (h[a] < h[b]) swap(a,b);
        ll k = h[a]-h[b];
        for (ll i = __lg(k); i >= 0; i--)
        {
            if (k >> i & 1)
            {   
                ans = max(ans, mx[a][i]);
                a = up[a][i];
            }
        }
    }
    if (a == b) return ans;
    for (ll i = 19; i >= 0; i--) 
    {
        if (up[a][i] != up[b][i]) 
        {
            ans = max({ans, mx[a][i], mx[b][i]});
            a = up[a][i]; b = up[b][i];
        }
    }
    return max({ans, mx[a][0], mx[b][0]});
}
ll rmn(ll a, ll b)
{
    ll ans = 1e18;
    if (h[a] != h[b])
    {
        if (h[a] < h[b]) swap(a,b);
        ll k = h[a]-h[b];
        for (ll i = __lg(k); i >= 0; i--)
        {
            if (k >> i & 1)
            {   
                ans = min(ans, mn[a][i]);
                a = up[a][i];
            }
        }
    }
    if (a == b) return ans;
    for (ll i = 19; i >= 0; i--) 
    {
        if (up[a][i] != up[b][i]) 
        {
            ans = min({ans, mn[a][i], mn[b][i]});
            a = up[a][i]; b = up[b][i];
        }
    }
    return min({ans, mn[a][0], mn[b][0]});
}
struct query {char c; ll l, r;};
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> q;
    if (n <= 4000)
    {
        for (ll i = 1; i <= n; i++) {v[i].pb(i); cnt[i]++;}
        for (ll i = 1; i < q+n; i++)
        {
            char c; cin >> c;
            if (c == 'C')
            {
                ll x; cin >> x;
                cout << cnt[x] << '\n';
            }
            else if (c == 'Q')
            {
                ll x, y; cin >> x >> y;
                bool ck = 0;
                for (ll j : v[x]) if (j == y) ck = 1;
                if (ck) cout << "yes" << '\n';
                else cout << "no" << '\n';
            }
            else 
            {
                ll a, b; cin >> a >> b;
                if (v[a].size() > v[b].size()) swap(a,b);
                vector<ll> tmp = v[a];
                for (ll j : v[b]) 
                {
                    v[a].pb(j);
                    cnt[j]++;
                }
                for (ll j : tmp)
                {
                    v[b].pb(j);
                    cnt[j]++;
                }
            }   
        }
    }    
    else
    {
        vector<query> qx;
        bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
        for (ll i = 1; i < q+n; i++)
        {
            char c; cin >> c;
            if (c == 'C') 
            {
                ll x; cin >> x;
                qx.pb({c,x,0});
            }
            else if (c == 'Q')
            {
                ll x, y; cin >> x >> y;
                qx.pb({c,x,y});
            }
            else
            {
                ll a, b; cin >> a >> b;
                if (a > b) swap(a,b);
                qx.pb({c,a,b});
                if (a != 1) ck_s2 = 0; 
                if (b-a != 1) ck_s3 = 0;
                if ((a<<1) != b && (a<<1|1) != b) ck_s4 = 0;
            }
        }
        if (ck_s2) // ck_s2
        {
            ll cnt_connected = tl[1] = 1;
            for (query i : qx)
            {
                if (i.c == 'S') tl[i.r] = ++cnt_connected;
                else if (i.c == 'C')
                {
                    if (i.l == 1) cout << cnt_connected << '\n';
                    else cout << cnt_connected-tl[i.l]+1 << '\n';
                }
                else
                {
                    if (i.l == i.r) cout << "yes" << '\n';
                    else if (i.l == 1)
                    {
                        if (tl[i.r]) cout << "yes" << '\n';
                        else cout << "no" << '\n';
                    }
                    else if (i.r == 1)
                    {
                        if (tl[i.l]) cout << "yes" << '\n';
                        else cout << "no" << '\n';
                    }
                    else if (!tl[i.l] || !tl[i.r]) cout << "no" << '\n';
                    else
                    {
                        if (tl[i.l] < tl[i.r]) cout << "no" << '\n';
                        else cout << "yes" << '\n';
                    }
                }
            }
        }
        else if (0) // ck_s3
        {
            
        }
        else
        {
            // cerr << "50%" << '\n';
            ll til = 0;
            for (query i : qx)
            {
                til++;
                if (i.c == 'S')
                {
                    g[i.l].pb({i.r,til});
                    g[i.r].pb({i.l,til});
                }
            }
            dfs(1,1); build_lca(); til = 0;
            // cerr << lds_ck(3,1);
            for (query i : qx)
            {
                til++;
                if (i.c == 'Q')
                {
                    ll l = lca(i.l, i.r);
                    ll dl = h[i.l]-h[l], dr = h[i.r]-h[l];
                    // cerr << i.l << ' ' << i.r << ' ' << l << ' ' << dl << ' ' << dr << '\n';
                    bool liss = lis_ck(i.r, dr), ldss = lds_ck(i.l, dl);
                    // cerr << liss << ' ' << ldss << '\n';
                    if (liss && ldss && rmn(i.l,l) > rmx(i.r,l) && rmx(i.l,i.r) <= til) cout << "yes" << '\n';
                    else cout << "no" << '\n';
                }
            }
        }
    }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:176:25: warning: variable 'ck_s3' set but not used [-Wunused-but-set-variable]
  176 |         bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
      |                         ^~~~~
servers.cpp:176:36: warning: variable 'ck_s4' set but not used [-Wunused-but-set-variable]
  176 |         bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
      |                                    ^~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4444 KB Output is correct
2 Correct 22 ms 5468 KB Output is correct
3 Correct 46 ms 16304 KB Output is correct
4 Correct 21 ms 5456 KB Output is correct
5 Correct 21 ms 5212 KB Output is correct
6 Correct 201 ms 79432 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4444 KB Output is correct
2 Correct 22 ms 5468 KB Output is correct
3 Correct 46 ms 16304 KB Output is correct
4 Correct 21 ms 5456 KB Output is correct
5 Correct 21 ms 5212 KB Output is correct
6 Correct 201 ms 79432 KB Output is correct
7 Correct 15 ms 4600 KB Output is correct
8 Correct 19 ms 5200 KB Output is correct
9 Correct 41 ms 19260 KB Output is correct
10 Correct 19 ms 4956 KB Output is correct
11 Correct 19 ms 4952 KB Output is correct
12 Correct 131 ms 79188 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4696 KB Output is correct
2 Correct 39 ms 13240 KB Output is correct
3 Correct 39 ms 13244 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4696 KB Output is correct
2 Correct 39 ms 13240 KB Output is correct
3 Correct 39 ms 13244 KB Output is correct
4 Correct 16 ms 4440 KB Output is correct
5 Incorrect 44 ms 13104 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4444 KB Output is correct
2 Correct 162 ms 88340 KB Output is correct
3 Correct 173 ms 88508 KB Output is correct
4 Correct 190 ms 87736 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4444 KB Output is correct
2 Correct 162 ms 88340 KB Output is correct
3 Correct 173 ms 88508 KB Output is correct
4 Correct 190 ms 87736 KB Output is correct
5 Correct 13 ms 4440 KB Output is correct
6 Incorrect 147 ms 87732 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4440 KB Output is correct
2 Correct 161 ms 81536 KB Output is correct
3 Correct 156 ms 81848 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4440 KB Output is correct
2 Correct 161 ms 81536 KB Output is correct
3 Correct 156 ms 81848 KB Output is correct
4 Correct 15 ms 4440 KB Output is correct
5 Incorrect 138 ms 80964 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4440 KB Output is correct
2 Correct 174 ms 88500 KB Output is correct
3 Correct 163 ms 88500 KB Output is correct
4 Correct 205 ms 87592 KB Output is correct
5 Correct 22 ms 4440 KB Output is correct
6 Correct 169 ms 81332 KB Output is correct
7 Correct 145 ms 81656 KB Output is correct
8 Correct 238 ms 82616 KB Output is correct
9 Correct 173 ms 82468 KB Output is correct
10 Correct 194 ms 85848 KB Output is correct
11 Correct 245 ms 85436 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4440 KB Output is correct
2 Correct 174 ms 88500 KB Output is correct
3 Correct 163 ms 88500 KB Output is correct
4 Correct 205 ms 87592 KB Output is correct
5 Correct 22 ms 4440 KB Output is correct
6 Correct 169 ms 81332 KB Output is correct
7 Correct 145 ms 81656 KB Output is correct
8 Correct 238 ms 82616 KB Output is correct
9 Correct 173 ms 82468 KB Output is correct
10 Correct 194 ms 85848 KB Output is correct
11 Correct 245 ms 85436 KB Output is correct
12 Correct 19 ms 4696 KB Output is correct
13 Incorrect 143 ms 87840 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4444 KB Output is correct
2 Correct 18 ms 5464 KB Output is correct
3 Correct 46 ms 16208 KB Output is correct
4 Correct 18 ms 5492 KB Output is correct
5 Correct 18 ms 5208 KB Output is correct
6 Correct 184 ms 79444 KB Output is correct
7 Correct 15 ms 4440 KB Output is correct
8 Correct 34 ms 13124 KB Output is correct
9 Correct 35 ms 13252 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 162 ms 88392 KB Output is correct
12 Correct 151 ms 88500 KB Output is correct
13 Correct 178 ms 87620 KB Output is correct
14 Correct 13 ms 4464 KB Output is correct
15 Correct 151 ms 81504 KB Output is correct
16 Correct 149 ms 81844 KB Output is correct
17 Correct 188 ms 82484 KB Output is correct
18 Correct 167 ms 82780 KB Output is correct
19 Correct 185 ms 85940 KB Output is correct
20 Correct 246 ms 85176 KB Output is correct
21 Correct 227 ms 80308 KB Output is correct
22 Correct 160 ms 81080 KB Output is correct
23 Correct 153 ms 80996 KB Output is correct
24 Correct 168 ms 81336 KB Output is correct
25 Correct 173 ms 82616 KB Output is correct
26 Correct 147 ms 80820 KB Output is correct
27 Correct 146 ms 80956 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4444 KB Output is correct
2 Correct 18 ms 5464 KB Output is correct
3 Correct 46 ms 16208 KB Output is correct
4 Correct 18 ms 5492 KB Output is correct
5 Correct 18 ms 5208 KB Output is correct
6 Correct 184 ms 79444 KB Output is correct
7 Correct 15 ms 4440 KB Output is correct
8 Correct 34 ms 13124 KB Output is correct
9 Correct 35 ms 13252 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 162 ms 88392 KB Output is correct
12 Correct 151 ms 88500 KB Output is correct
13 Correct 178 ms 87620 KB Output is correct
14 Correct 13 ms 4464 KB Output is correct
15 Correct 151 ms 81504 KB Output is correct
16 Correct 149 ms 81844 KB Output is correct
17 Correct 188 ms 82484 KB Output is correct
18 Correct 167 ms 82780 KB Output is correct
19 Correct 185 ms 85940 KB Output is correct
20 Correct 246 ms 85176 KB Output is correct
21 Correct 227 ms 80308 KB Output is correct
22 Correct 160 ms 81080 KB Output is correct
23 Correct 153 ms 80996 KB Output is correct
24 Correct 168 ms 81336 KB Output is correct
25 Correct 173 ms 82616 KB Output is correct
26 Correct 147 ms 80820 KB Output is correct
27 Correct 146 ms 80956 KB Output is correct
28 Correct 15 ms 4444 KB Output is correct
29 Correct 20 ms 5212 KB Output is correct
30 Correct 42 ms 19280 KB Output is correct
31 Correct 19 ms 4968 KB Output is correct
32 Correct 19 ms 4952 KB Output is correct
33 Correct 129 ms 79216 KB Output is correct
34 Correct 16 ms 4444 KB Output is correct
35 Incorrect 39 ms 13256 KB Extra information in the output file
36 Halted 0 ms 0 KB -