Submission #402363

#	Time	Username	Problem	Language	Result	Execution time	Memory
402363		doowey	Inside information (BOI21_servers)	C++14	0 / 100	1961 ms	524292 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 = 120101;
vector<pii> T[N];
vector<pii> qq[N];
vector<int> cnt[N];

bool del[N];
int sub[N];

int num[N];
int iq[N];
int iter;
bool inc[N];
bool dem[N];

int outp[N];
int in[N];

ll shd[N];

void dfs(int u, int pa){
    sub[u]=1;
    num[u]=-1;
    iq[u]=iter;
    for(auto x : T[u]){
        if(x.fi==pa || del[x.fi]) continue;
        dfs(x.fi, u);
        sub[u] += sub[x.fi];
    }
}

void dfs2(int u, int pa, int ss, int l1, int l2){
    num[u] = ss;
    in[u] = l2;
    if(l1 == -1 || l2 == -1) inc[u]=dem[u]=true;
    else{
        if(l1 > l2){
            inc[u]=inc[pa];
            dem[u]=false;
        }
        else{
            inc[u]=false;
            dem[u]=dem[pa];
        }
    }
    for(auto x : qq[u]){
        if(iq[x.fi] == iq[u]){
            if(num[x.fi] == 0){
                if(inc[u] && shd[ss] <= x.se){
                    outp[x.se] = -1;
                }
                else{
                    outp[x.se] = -2;
                }
            }
            else if(num[x.fi] == -1){
                outp[x.se] = -2;
            }
            else if(num[u] != num[x.fi]){
                if(inc[u] && dem[x.fi] && in[x.fi] <= x.se){
                    outp[x.se] = -1;
                }
                else{
                    outp[x.se] = -2;
                }
            }
        }
    }
    for(auto x : T[u]){
        if(x.fi==pa || del[x.fi]) continue;
        dfs2(x.fi, u, ss, l2, x.se);
    }
}

bool comp(pii a, pii b){
    return a.se > b.se;
}

bool getans(int x, int y, int pp, int mx, int las){
    bool sol = false;
    if(x == y) return true;
    for(auto v : T[x]){
        if(v.fi == pp || las > v.se || v.se > mx) continue;
        sol |= getans(v.fi, y, x, mx, v.se);
    }
    return sol;
}

void decomp(int node){
    iter ++ ;
    dfs(node, -1);
    int pp = -1;
    bool go = true;
    int sz = sub[node];
    while(go){
        go = false;
        for(auto x : T[node]){
            if(x.fi == pp || del[x.fi]) continue;
            if(sub[x.fi] > sz / 2){
                go = true;
                pp = node;
                node = x.fi;
                break;
            }
        }
    }
    sort(T[node].begin(), T[node].end(), comp);
    num[node] = 0;
    int cc = 1;
    inc[node]=dem[node]=true;
    for(auto x : T[node]){
        if(del[x.fi]) continue;
        shd[cc] = x.se;
        dfs2(x.fi, node, cc, -1, x.se);
        cc ++ ;
    }
    for(auto x : qq[node]){
        if(iq[node] == iq[x.fi]){

            if(dem[x.fi] && in[x.fi] <= x.se){
                outp[x.se] = -1;
            }
            else{
                outp[x.se] = -2;
            }
        }
    }
    del[node]=true;

    for(auto x : T[node]){
        if(!del[x.fi])
            decomp(x.fi);
    }
}

int ex[N];

int main(){
    fastIO;
    freopen("in.txt", "r", stdin);
    int n, q;
    cin >> n >> q;
    char typ;
    int x, y;
    for(int iq = 1; iq <= n + q - 1; iq ++ ){
        cin >> typ;
        if(typ == 'S'){
            cin >> x >> y;
            T[x].push_back(mp(y, iq));
            T[y].push_back(mp(x, iq));
        }
        else if(typ == 'Q'){
            cin >> x >> y; // is there an increasing path from y to x
            outp[iq]=-2;
            ex[iq] = getans(y, x, -1, iq, 0);
            if(ex[iq] == 1) ex[iq] = -1;
            else ex[iq] = -2;
            if(x == y){
                outp[iq] = -1;
            }
            else{
                qq[y].push_back(mp(x, iq));
            }
        }
        else{
            cin >> x;
            cnt[x].push_back(iq);
        }
    }
    //decomp(1);
    for(int oo = 1; oo <= n + q - 1; oo ++ ){
        if(ex[oo] == -1){
            cout << "yes\n";
        }
        else{
            cout << "no\n";
        }
    }
    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:151:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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