Submission #410760

#	Time	Username	Problem	Language	Result	Execution time	Memory
410760		Ruxandra985	Inside information (BOI21_servers)	C++14	0 / 100	59 ms	5640 KiB

servers

#include <bits/stdc++.h>
#define DIMN 120010
using namespace std;
int elem;
int rmq_lca[20][2*DIMN] , eul[2*DIMN] , first[DIMN] , nv[2*DIMN] , logg[2*DIMN];
int rmqc[20][DIMN] , rmqd[20][DIMN] , rmqt[20][DIMN] , maxi[20][DIMN];
vector <pair <int , int> > v[DIMN];

pair <int , int> tt[DIMN];

struct queryuri{

    int x , y , mch;

} qry[DIMN];

void dfs (int nod , int fth , int val , int lvl){
    int i , vecin , cost;
    eul[++elem] = nod;
    first[nod] = elem;
    nv[elem] = lvl;

    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i].first;
        cost = v[nod][i].second;

        if (vecin == fth){

            tt[nod] = make_pair(vecin , val);
            continue;

        }

        dfs(vecin , nod , cost , lvl + 1);
        eul[++elem] = nod;
        nv[elem] = lvl;
    }

}

int query (int x, int y){
    int px , py , len;

    px = first[x];
    py = first[y];

    if (px > py)
        swap(px , py);

    len = py - px + 1;
    len = logg[len]; /// cea mai mare p2 <= len

    if (nv[ rmq_lca[len][px] ] < nv[ rmq_lca[len][py - (1 << len) + 1] ])
        return eul[rmq_lca[len][px]];
    else return eul[rmq_lca[len][py - (1 << len) + 1]];

}

int qmaxi (int x , int y){
    int p2 , val = 0;
    for (p2 = 19 ; p2 >= 0 ; p2--){

        if (nv[x] - (1 << p2) >= nv[y]){
            val = max(val , maxi[p2][x]);
            x = rmqt[p2][x];
        }

    }

    return val;


}

int ok (int x , int y , int fth){
    int p2 , val = 1 , y2 , x2;
    y2 = y;
    for (p2 = 19 ; p2 >= 0 ; p2--){

        if (nv[y] - (1 << p2) >= nv[fth]){
            val = (val & rmqc[p2][y]);
            y = rmqt[p2][fth];
        }

    }

    if (!val)
        return 0;

    val = 1;
    x2 = x;

    for (p2 = 19 ; p2 >= 0 ; p2--){

        if (nv[x] - (1 << p2) >= nv[fth]){
            val = (val & rmqd[p2][x]);
            x = rmqt[p2][x];
        }

    }

    if (!val)
        return 0;

    if (x2 == fth || y2 == fth)
        return 1;

    for (p2 = 19 ; p2 >= 0 ; p2--){

        if (nv[x2] - (1 << p2) > nv[fth])
            x2 = rmqt[p2][x2];

        if (nv[y2] - (1 << p2) > nv[fth])
            y2 = rmqt[p2][y2];

    }

    return tt[y2].second < tt[x2].second;

}



int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , q , cnt , i , x , y , mch = 0 , powe , fth , j , vecin;
    char c;
    fscanf (fin,"%d%d\n",&n,&q);
    cnt = 0;
    for (i = 1 ; i <= n + q - 1 ; i++){
        c = fgetc(fin);
        if ( c == 'S' ){

            fscanf (fin,"%d%d\n",&x,&y);
            mch++;
            v[x].push_back(make_pair(y , mch));
            v[y].push_back(make_pair(x , mch));

        }
        else if ( c == 'Q' ){

            fscanf (fin,"%d%d\n",&x,&y);
            qry[++cnt] = {x , y , mch};

        }
        else { /// momentan nimic

        }
    }


    /// vrei sa ai lca disponibil

    dfs (1 , 0 , 0 , 1);

    for (i = 2 ; i <= 2 * n ; i++)
        logg[i] = 1 + logg[i / 2];

    for (i = 1 ; i <= elem ; i++)
        rmq_lca[0][i] = i;

    for (powe = 1 ; (1 << powe) <= elem ; powe++){
        for (i = 1 ; i + (1 << powe) - 1 <= elem ; i++){

            if (nv[ rmq_lca[powe-1][i] ] < nv[ rmq_lca[powe-1][i + (1 << (powe - 1) )] ])
                rmq_lca[powe][i] = rmq_lca[powe-1][i];
            else rmq_lca[powe][i] = rmq_lca[powe-1][i + (1 << (powe - 1) )];

        }
    }


    for (i = 1 ; i <= n ; i++){
        rmqt[0][i] = tt[i].first;
    }
    for (powe = 1 ; (1 << powe) <= n ; powe++){
        for (i = 1 ; i <= n ; i++){

            rmqt[powe][i] = rmqt[powe - 1][rmqt[powe - 1][i]];

        }
    }



    /// imi va mai trb un rmqc si rmqd

    for (i = 1 ; i <= n ; i++){
        rmqc[0][i] = rmqd[0][i] = 1;
        maxi[0][i] = tt[i].second;
    }

    for (powe = 1 ; (1 << powe) <= n ; powe++){
        for (i = 1 ; i <= n ; i++){



            maxi[powe][i] = max(maxi[powe - 1][i] , maxi[powe - 1][ rmqt[powe - 1][i] ]);

            if (rmqc[powe-1][i] && rmqc[powe-1][ rmqt[powe - 1][i] ]){

                fth = rmqt[powe-1][i];

                for (j = 0 ; j < v[fth].size() ; j++){
                    vecin = v[fth][j].first;
                    if (vecin != tt[fth].first && query(i , vecin) == vecin){

                        if (v[fth][j].second < tt[rmqt[powe-1][i]].second)
                            rmqc[powe][i] = 1;

                        break;
                    }
                }


            }

            if (rmqd[powe-1][i] && rmqd[powe-1][ rmqt[powe - 1][i] ]){

                fth = rmqt[powe-1][i];

                for (j = 0 ; j < v[fth].size() ; j++){
                    vecin = v[fth][j].first;
                    if (vecin != tt[fth].first && query(i , vecin) == vecin){

                        if (v[fth][j].second > tt[rmqt[powe-1][i]].second)
                            rmqd[powe][i] = 1;

                        break;
                    }
                }


            }

        }
    }

    /// momentul sa rasp la queryuri?

    for (i = 1 ; i <= cnt ; i++){

        x = qry[i].x;
        y = qry[i].y;
        mch = qry[i].mch;

        fth = query(x , y);

        if (qmaxi(x , fth) > mch || qmaxi(y , fth) > mch){
            fprintf (fout,"no\n"); /// maximul prea mare
            continue;
        }

        if (ok(x , y , fth))
            fprintf (fout,"yes\n");
        else fprintf (fout,"no\n");

    }

    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'void dfs(int, int, int, int)':
servers.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (i = 0 ; i < v[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:206:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |                 for (j = 0 ; j < v[fth].size() ; j++){
      |                              ~~^~~~~~~~~~~~~~~
servers.cpp:224:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |                 for (j = 0 ; j < v[fth].size() ; j++){
      |                              ~~^~~~~~~~~~~~~~~
servers.cpp:130:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     fscanf (fin,"%d%d\n",&n,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:136:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |             fscanf (fin,"%d%d\n",&x,&y);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:144:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |             fscanf (fin,"%d%d\n",&x,&y);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• 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