oj.uz

Submission #1067067

# Submission time Handle Problem Language Result Execution time Memory
1067067 2024-08-20T10:35:26 Z vjudge1 Inside information (BOI21_servers) C++17
0 / 100
 50 ms 8392 KB 
//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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1880 KB Output is correct
2 Incorrect 24 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1880 KB Output is correct
2 Incorrect 24 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1720 KB Output is correct
2 Incorrect 50 ms 8392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1720 KB Output is correct
2 Incorrect 50 ms 8392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1628 KB Output is correct
2 Incorrect 22 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1628 KB Output is correct
2 Incorrect 22 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -