oj.uz

Submission #1036715

# Submission time Handle Problem Language Result Execution time Memory
1036715 2024-07-27T15:57:25 Z vjudge1 Inside information (BOI21_servers) C++17
52.5 / 100
 240 ms 88568 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 (0) // 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:14: warning: variable 'ck_s2' set but not used [-Wunused-but-set-variable]
  176 |         bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
      |              ^~~~~
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 16 ms 4444 KB Output is correct
2 Correct 25 ms 5344 KB Output is correct
3 Correct 74 ms 16176 KB Output is correct
4 Correct 22 ms 5496 KB Output is correct
5 Correct 23 ms 5436 KB Output is correct
6 Correct 206 ms 79444 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4444 KB Output is correct
2 Correct 25 ms 5344 KB Output is correct
3 Correct 74 ms 16176 KB Output is correct
4 Correct 22 ms 5496 KB Output is correct
5 Correct 23 ms 5436 KB Output is correct
6 Correct 206 ms 79444 KB Output is correct
7 Correct 13 ms 4444 KB Output is correct
8 Correct 19 ms 5212 KB Output is correct
9 Correct 42 ms 19088 KB Output is correct
10 Correct 20 ms 4944 KB Output is correct
11 Correct 18 ms 4956 KB Output is correct
12 Correct 148 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 171 ms 79768 KB Output is correct
3 Correct 151 ms 79816 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 171 ms 79768 KB Output is correct
3 Correct 151 ms 79816 KB Output is correct
4 Correct 16 ms 4432 KB Output is correct
5 Incorrect 161 ms 79668 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 4440 KB Output is correct
2 Correct 151 ms 88568 KB Output is correct
3 Correct 166 ms 88500 KB Output is correct
4 Correct 188 ms 87804 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4440 KB Output is correct
2 Correct 151 ms 88568 KB Output is correct
3 Correct 166 ms 88500 KB Output is correct
4 Correct 188 ms 87804 KB Output is correct
5 Correct 27 ms 4424 KB Output is correct
6 Incorrect 149 ms 87884 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 20 ms 4440 KB Output is correct
2 Correct 157 ms 81336 KB Output is correct
3 Correct 153 ms 81716 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4440 KB Output is correct
2 Correct 157 ms 81336 KB Output is correct
3 Correct 153 ms 81716 KB Output is correct
4 Correct 16 ms 4548 KB Output is correct
5 Incorrect 129 ms 81004 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 15 ms 4444 KB Output is correct
2 Correct 162 ms 88424 KB Output is correct
3 Correct 193 ms 88504 KB Output is correct
4 Correct 182 ms 87732 KB Output is correct
5 Correct 17 ms 4444 KB Output is correct
6 Correct 152 ms 81336 KB Output is correct
7 Correct 168 ms 82088 KB Output is correct
8 Correct 188 ms 82544 KB Output is correct
9 Correct 169 ms 82532 KB Output is correct
10 Correct 177 ms 85784 KB Output is correct
11 Correct 240 ms 85192 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4444 KB Output is correct
2 Correct 162 ms 88424 KB Output is correct
3 Correct 193 ms 88504 KB Output is correct
4 Correct 182 ms 87732 KB Output is correct
5 Correct 17 ms 4444 KB Output is correct
6 Correct 152 ms 81336 KB Output is correct
7 Correct 168 ms 82088 KB Output is correct
8 Correct 188 ms 82544 KB Output is correct
9 Correct 169 ms 82532 KB Output is correct
10 Correct 177 ms 85784 KB Output is correct
11 Correct 240 ms 85192 KB Output is correct
12 Correct 17 ms 4444 KB Output is correct
13 Incorrect 141 ms 87796 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 16 ms 4440 KB Output is correct
2 Correct 21 ms 5560 KB Output is correct
3 Correct 45 ms 16208 KB Output is correct
4 Correct 21 ms 5456 KB Output is correct
5 Correct 21 ms 5196 KB Output is correct
6 Correct 195 ms 79440 KB Output is correct
7 Correct 19 ms 4444 KB Output is correct
8 Correct 144 ms 79704 KB Output is correct
9 Correct 143 ms 79720 KB Output is correct
10 Correct 19 ms 4444 KB Output is correct
11 Correct 150 ms 88516 KB Output is correct
12 Correct 154 ms 88504 KB Output is correct
13 Correct 186 ms 87696 KB Output is correct
14 Correct 22 ms 4640 KB Output is correct
15 Correct 155 ms 81340 KB Output is correct
16 Correct 145 ms 81832 KB Output is correct
17 Correct 186 ms 82548 KB Output is correct
18 Correct 151 ms 82616 KB Output is correct
19 Correct 181 ms 85944 KB Output is correct
20 Correct 224 ms 85188 KB Output is correct
21 Correct 149 ms 80312 KB Output is correct
22 Correct 146 ms 81180 KB Output is correct
23 Correct 151 ms 81084 KB Output is correct
24 Correct 156 ms 81336 KB Output is correct
25 Correct 166 ms 82616 KB Output is correct
26 Correct 139 ms 80960 KB Output is correct
27 Correct 141 ms 80968 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4440 KB Output is correct
2 Correct 21 ms 5560 KB Output is correct
3 Correct 45 ms 16208 KB Output is correct
4 Correct 21 ms 5456 KB Output is correct
5 Correct 21 ms 5196 KB Output is correct
6 Correct 195 ms 79440 KB Output is correct
7 Correct 19 ms 4444 KB Output is correct
8 Correct 144 ms 79704 KB Output is correct
9 Correct 143 ms 79720 KB Output is correct
10 Correct 19 ms 4444 KB Output is correct
11 Correct 150 ms 88516 KB Output is correct
12 Correct 154 ms 88504 KB Output is correct
13 Correct 186 ms 87696 KB Output is correct
14 Correct 22 ms 4640 KB Output is correct
15 Correct 155 ms 81340 KB Output is correct
16 Correct 145 ms 81832 KB Output is correct
17 Correct 186 ms 82548 KB Output is correct
18 Correct 151 ms 82616 KB Output is correct
19 Correct 181 ms 85944 KB Output is correct
20 Correct 224 ms 85188 KB Output is correct
21 Correct 149 ms 80312 KB Output is correct
22 Correct 146 ms 81180 KB Output is correct
23 Correct 151 ms 81084 KB Output is correct
24 Correct 156 ms 81336 KB Output is correct
25 Correct 166 ms 82616 KB Output is correct
26 Correct 139 ms 80960 KB Output is correct
27 Correct 141 ms 80968 KB Output is correct
28 Correct 15 ms 4444 KB Output is correct
29 Correct 19 ms 5212 KB Output is correct
30 Correct 40 ms 19072 KB Output is correct
31 Correct 20 ms 5060 KB Output is correct
32 Correct 18 ms 5040 KB Output is correct
33 Correct 126 ms 79232 KB Output is correct
34 Correct 16 ms 4444 KB Output is correct
35 Incorrect 133 ms 79544 KB Extra information in the output file
36 Halted 0 ms 0 KB -