제출 #1036715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036715		vjudge1	Inside information (BOI21_servers)	C++17	52.50 / 100	240 ms	88568 KiB

servers

#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';
                }
            }
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5