Submission #573846

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
573846	2022-06-07T10:22:43 Z	talant117408	Inside information (BOI21_servers)	C++17	2.5 / 100	127 ms	33148 KB

servers

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
 
int mod = 1e9+7;
 
ll modulo(ll a) {
    return ((a % mod) + mod) % mod;
}
 
ll add(ll a, ll b) {
    return modulo(a + b);
}
 
ll mult(ll a, ll b) {
    return modulo(a * b);
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 120007;
vector <pii> graph[N];
int tin[N], tout[N], timer, up[N][20], parent[N], lift[N][20];
int depth[N];
int n, k;

bool upper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

bool get(int a, int b, int time) {
    if (a == b) return true;
    if (upper(a, b)) {
        int lca = b, sum = 0;
        for (int bit = 19; ~bit; bit--) {
            if (!upper(up[lca][bit], a)) {
                sum += lift[lca][bit];
                lca = up[lca][bit];
            }
        }
        return (sum == 0 && parent[lca] <= time);
    }
    else if (upper(b, a)) {
        int lca = a, sum = 0;
        for (int bit = 19; ~bit; bit--) {
            if (!upper(up[lca][bit], a)) {
                sum += lift[lca][bit];
                lca = up[lca][bit];
            }
        }
        return (sum == depth[a]-depth[lca] && parent[a] <= time);
    }
    int suma = 0, sumb = 0, lcaa = a, lcab = b;
    for (int bit = 19; ~bit; bit--) {
        if (!upper(up[lcab][bit], a)) {
            sumb += lift[lcab][bit];
            lcab = up[lcab][bit];
        }
        if (!upper(up[lcaa][bit], b)) {
            suma += lift[lcaa][bit];
            lcaa = up[lcaa][bit];
        }
    }
    return (suma == depth[a]-depth[lcaa] && sumb == 0 && parent[lcaa] > parent[lcab] && parent[a] <= time);
}

void dfs(int v, int p) {
    tin[v] = ++timer;
    up[v][0] = p;
    lift[v][0] = (parent[v] > parent[up[v][0]]);
    for (int i = 1; i < 20; i++) {
        up[v][i] = up[up[v][i-1]][i-1];
        lift[v][i] = lift[v][i-1] + lift[up[v][i-1]][i-1];
    }
    for (auto x : graph[v]) {
        if (x.first == p) continue;
        parent[x.first] = x.second;
        depth[x.first] = depth[v] + 1;
        dfs(x.first, v);
    }
    tout[v] = ++timer;
}

void solve() {
    cin >> n >> k;
    int time = 0;
    vector <array <int, 3>> q;
    for (int i = 0; i < n+k-1; i++) {
        char tmp;
        cin >> tmp;
        if (tmp == 'C') {
            int a;
            cin >> a;
        }
        else {
            int a, b;
            cin >> a >> b;
            if (tmp == 'S') {
                time++;
                graph[a].pb(mp(b, time));
                graph[b].pb(mp(a, time));
            }
            else {
                q.pb({a, b, time});
            }
        }
    }
    dfs(1, 1);
    for (auto to : q) {
        if (get(to[0], to[1], to[2])) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*
4 4
S 1 2
S 1 3
S 3 4
Q 2 1
Q 2 2
Q 2 3
Q 2 4
*/

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	5056 KB	Output is correct
2	Correct	123 ms	33104 KB	Output is correct
3	Correct	127 ms	33148 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	5056 KB	Output is correct
2	Correct	123 ms	33104 KB	Output is correct
3	Correct	127 ms	33148 KB	Output is correct
4	Incorrect	31 ms	5824 KB	Extra information in the output file
5	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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

Submission #573846

Compilation message