Submission #402387

#	Time	Username	Problem	Language	Result	Execution time	Memory
402387		doowey	Inside information (BOI21_servers)	C++14	2.50 / 100	3606 ms	11616 KiB

servers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 120100;
const int M = N * 2;
vector<pii> T[N];

int bruh[M];

bool chk(int node, int par, int target, int las){
    if(node == target) return true;
    for(auto x : T[node]){
        if(x.fi == par || x.se < las) continue;
        if(chk(x.fi, node, target, x.se))
            return true;
    }
    return false;
}


int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    char typ;
    int xx, yy;
    bool sol;
    for(int iq = 1; iq <= n + q - 1; iq ++ ){
        cin >> typ;
        if(typ == 'S'){
            cin >> xx >> yy;
            T[xx].push_back(mp(yy, iq));
            T[yy].push_back(mp(xx, iq));
        }
        else{
            cin >> xx >> yy;
            sol = chk(yy, -1, xx, 0);
            if(sol == true){
                bruh[iq] = -1;
            }
            else{
                bruh[iq] = -2;
            }
        }
    }
    for(int i = 1; i <= n + q - 1; i ++ ){
        if(bruh[i] == 0) continue;
        if(bruh[i] == -1){
            cout << "yes\n";
        }
        else if(bruh[i] == -2){
            cout << "no\n";
        }
        else{
            cout << bruh[i] << "\n";
        }
    }
    return 0;
}

• Subtask 1: 2.5 / 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