Submission #1067067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067067		vjudge1	Inside information (BOI21_servers)	C++17	0 / 100	50 ms	8392 KiB

servers

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50;

struct DSU {
    vi dad,change,sz;
    DSU(int nn){
        dad.resize(nn+1);
        iota(all(dad),0ll);
        change.assign(nn+1,0);
        sz.assign(nn+1,1);
    }
    int find(int x,int t) {
        if (!change[x] || change[x] > t) return x;
        return find(dad[x],t);
    }
    void unite(int x,int y,int t) {
        int a = find(x,t);
        int b = find(y,t);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a,b);
        dad[b] = a;
        change[b] = t;
        sz[a]+=sz[b];
    }
}; 
void solve() { 
    int n,q;
    cin >> n >> q;
    q+=n-1;
    int cc = 0;
    vector<pii> edg;
    edg.push_back({0,0});
    DSU dsu(n);
    while (q--) {
        char t;
        cin >> t;
        if (t == 'S') {
            int a,b;
            cin >> a >> b;
            dsu.unite(a,b,++cc);
            edg.push_back({a,b});
        }
        if (t == 'Q') {
            int a,x;
            cin >> a >> x;
            int l = 1,r = cc;
            while (l<=r) {
                int m = (l+r) >> 1;
                if (dsu.find(a,m) == dsu.find(x,m)) r = m-1;
                else l = m+1;
            }
            if (l > cc) {
                cout << "no\n";
                continue;
            }
            if (edg[l].ff == a || edg[l].ss == a) {
                cout << "yes\n";
                continue;
            } else cout << "no\n";
        }
        if (t == 'C') {

            assert(0);
        }
    }
}
 
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5