Submission #655589

#	Time	Username	Problem	Language	Result	Execution time	Memory
655589		600Mihnea	Inside information (BOI21_servers)	C++17	62.50 / 100	3567 ms	100600 KiB

servers

#include <bits/stdc++.h>

using namespace std;

const int N=240000+7;
const int K = 20;
int n;
int k;
vector<pair<int, int>> gg[N];
vector<pair<int,int>> q2[N];
int q1[N];
int p[N];
int pskip[K][N];
int dep[N];
int euler_tour[2 * N];
int tour_sz;
int first_time_on_tour[N];
int last_time_on_tour[N];
int lg2[2 * N];
int idup[N];
//vector<int> g[N];
pair<int, int> tab_lca[2 * N][K];
vector<int> who_have_id[N];
int who_has_id[N];

void dfs_lca(int a, int par = 0)
{
    p[a] = par;
    euler_tour[++tour_sz] = a;
    first_time_on_tour[a] = last_time_on_tour[a] = tour_sz;
    vector<pair<int, int>> ngg;
    for (auto &it : gg[a])
    {
        int b=it.first;
        int i=it.second;

        if (b==par){
                continue;
        }
        ngg.push_back(it);
        who_has_id[i]=b;
        idup[b]=i;
        dep[b] = 1 + dep[a];
        dfs_lca(b, a);
        euler_tour[++tour_sz] = a;
        last_time_on_tour[a] = tour_sz;
    }
    gg[a]=ngg;
}

void lcaTM()
{
    dfs_lca(1);
    for (int i = 2; i <= tour_sz; i++)
    {
        lg2[i] = 1 + lg2[i / 2];
    }
    for (int i = 1; i <= tour_sz; i++)
    {
        tab_lca[i][0] = {dep[euler_tour[i]], euler_tour[i]};
    }
    for (int k = 1; (1 << k) <= tour_sz; k++)
    {
        for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++)
        {
            tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int lca(int a, int b)
{
    if (first_time_on_tour[a] > last_time_on_tour[b])
    {
        swap(a, b);
    }
    a = first_time_on_tour[a];
    b = last_time_on_tour[b];
    int k = lg2[b - a + 1];
    return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second;
}

int goup(int a,int cnt){
        assert(cnt>=0);
        for(int i=0;i<K;i++){
                if(cnt&(1<<i)){
                        a=pskip[i][a];
                }
        }
        return a;
}

int sol[N];
int tp[N];
int inc[N];
int dcr[N];
int cnt[N];

void dfs2(int a){
        inc[a]=max(inc[a],1);
        dcr[a]=max(dcr[a],1);
        for (auto &it:gg[a]){
                int b=it.first;
                if(b==p[a]){
                        continue;
                }
                if(idup[a]<idup[b]){
                        inc[b]=1+inc[a];
                }else{
                        dcr[b]=1+dcr[a];
                }
                dfs2(b);
        }
        ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n";
}

int main() {
        if(0){
                freopen("them.txt","r",stdin);
                freopen("output2.txt","w",stdout);
                /*char s[1000];
                while(cin.getline(s,1000)){
                        if(s[0]!='Q'){
                                cout<<s<<"\n";
                        }
                }*/
                string s;
                while(cin>>s){
                        if(s=="yes"||s=="no"){
                                continue;
                        }
                        cout<<s<<"\n";
                }

                exit(0);
        }
if(1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
else {
                freopen("___input___.txt","r",stdin);
               /// freopen("them.txt","r",stdin);
                if(0)freopen("out.txt","w",stdout);

}
        cin>>n>>k;

        int cnt3=0;
        for(int i=1;i<=n+k-1;i++){
                string s;
                cin>>s;
                assert(s=="S"||s=="Q"||s=="C");
                if(s=="S"){
                        tp[i]=2;
                        int a,b;
                        cin>>a>>b;
                        ///g[a].push_back(b);
                        ///g[b].push_back(a);
                        gg[a].push_back({b, i});
                        gg[b].push_back({a, i});
                        sol[i]=-1;
                }
                if(s=="Q"){
                        int a,b;
                        cin>>a>>b;
                        if(a==b){
                                tp[i]=1;
                                sol[i]=1;
                        }else{
                                q2[a].push_back({b, i});
                                tp[i]=1;
                                sol[i]=-2;
                        }
                }
                if(s=="C"){
                        cnt3++;
                        int a;
                        cin>>a;
                     ///   cout<<i<<" = "<<a<<"\n";
                        q1[i]=a;
                        sol[i]=-3;
                        tp[i]=3;
                }
        }

        lcaTM();
        dfs2(1);
        /// solve q1 for the general case

        for (int i=1;i<=n;i++){
                pskip[0][i]=p[i];
        }
        for (int k=1;k<K;k++){
                for (int i=1;i<=n;i++){
                        pskip[k][i]=pskip[k-1][pskip[k-1][i]];
                }
        }


        for (int a=1;a<=n;a++){
                for (auto &it:q2[a]){
                        int b=it.first,i=it.second;
                        /**

                        **/
                        /// drumul de la b la a e crescator?
                        vector<int> guys_x,guys_y;
                        int x=a,y=b,z;
                        swap(x,y);
                        z=lca(x,y);
                        int last=-1;
                        if(y!=z){
                                last=idup[y];
                        }else{
                                last=idup[goup(x,dep[x]-dep[z]-1)];
                        }
                        bool ok=1;
                        ok&=(inc[y]>=dep[y]-dep[z]);
                        ok&=(dcr[x]>=dep[x]-dep[z]);
                        if(x!=z&&y!=z){
                                ok&=(idup[goup(x,dep[x]-dep[z]-1)]<=idup[goup(y,dep[y]-dep[z]-1)]);
                        }
                        ok&=(last<i);
                        sol[i]=ok;
                }
        }

        const int INF=(int)1e9+7;

        int cnt_2=0;
        int ciq=0;

//        assert(p[2]==21);
 //       assert(p[25]==21);

       // cout<<"sir = "<<idup[46]<<" "<<idup[2]<<" "<<idup[21]<<"\n";
        for (int i=1;i<=n+k-1&&cnt3!=0;i++){
                if(tp[i]==2){
                        cnt_2++;
                        /// add edge
                        int vertex=who_has_id[i],last=+INF;

                      //  cout<<vertex<<" "<<p[vertex]<<"\n";


                        while(p[vertex]){
                                if(idup[vertex]>last){
                                        break;
                                }
                                last=idup[vertex];
                                cnt[vertex]++;

                                vertex=p[vertex];
                        }
                }
                if (q1[i]){
                        ciq++;
                        assert(tp[i]==3);
                        int vertex=q1[i];
                        int ret=1,last=-INF;
                        int init=vertex;

                        for (auto &it : gg[vertex]){
                                int v2=it.first;
                                ret+=cnt[v2];
                        }

                        while (p[vertex]){
                                if (idup[vertex]<last){
                                        break;
                                }
                                ret+=(idup[vertex]<i);
                                for (auto &it:gg[p[vertex]]){
                                        int v2=it.first;
                                        if(idup[vertex]<idup[v2]){
                                                ret+=cnt[v2];
                                        }
                                }
                                last=idup[vertex];
                                vertex=p[vertex];
                        }

                        sol[i]=ret;

                        if(ciq==194){
                           //     cout<<"ret = "<<ret<<", query = "<<init<<"\n";
                           //    return 0;
                        }
                }
        }
        if(cnt3)
        assert(cnt_2==n-1);


        for (int i=1;i<=n+k-1;i++){
                if(tp[i]==1){
                        assert(sol[i]==0||sol[i]==1);

                        ///continue;
                        if(sol[i]==1){
                                cout<<"yes\n";
                        }else{
                                cout<<"no\n";
                        }
                }
                if (tp[i]==3){
                        cout<<sol[i]<<"\n";
                }
        }

        return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:259:29: warning: unused variable 'init' [-Wunused-variable]
  259 |                         int init=vertex;
      |                             ^~~~
servers.cpp:119:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |                 freopen("them.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:120:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 freopen("output2.txt","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:139:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |                 freopen("___input___.txt","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:141:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |                 if(0)freopen("out.txt","w",stdout);
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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