제출 #411163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411163		Ruxandra985	Inside information (BOI21_servers)	C++14	50 / 100	482 ms	76992 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] , niv[DIMN];
int rmqc[20][DIMN] , rmqd[20][DIMN] , rmqt[20][DIMN] , maxi[20][DIMN];
int help[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;
    niv[nod] = 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 (niv[x] - (1 << p2) >= niv[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 , j , vecin;
    y2 = y;
    for (p2 = 19 ; p2 >= 0 ; p2--){

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

            /// este cazul sa fac verificarea?
            if (y != fth){

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

                        if (v[y][j].second < tt[y].second)
                            break;
                        else return 0;

                    }
                }

            }


        }

    }

    if (!val)
        return 0;

    val = 1;
    x2 = x;

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

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

            if (x != fth){

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

                        if (v[x][j].second > tt[x].second)
                            break;
                        else return 0;

                    }
                }

            }
        }

    }

    if (!val)
        return 0;

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

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

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

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

    }

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

}



int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    //FILE *in = fopen ("b.in", "r");
    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;

        help[0][i] = i;

    }

    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] ] && tt[help[powe - 1][i]].second < tt[rmqt[powe-1][i]].second)
                rmqc[powe][i] = 1;

            if (rmqd[powe-1][i] && rmqd[powe-1][ rmqt[powe - 1][i] ] && tt[help[powe - 1][i]].second > tt[rmqt[powe-1][i]].second)
                rmqd[powe][i] = 1;

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

        }
    }

    /// momentul sa rasp la queryuri?
    char ans[10];

    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 || !mch){
            //fscanf (in,"%s\n",ans);
            //if (ans[0] != 'n')
                //printf ("%d\n", i);
            fprintf (fout,"no\n"); /// maximul prea mare
            continue;
        }
        //fscanf (in,"%s\n",ans);
        if (ok(x , y , fth)){
            //if (ans[0] != 'y')
                //printf ("%d\n", i);
            fprintf (fout,"yes\n");
        }
        else {
            //if (ans[0] != 'n')
              //  printf ("%d\n", i);
            fprintf (fout,"no\n");
        }

    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'void dfs(int, int, int, int)':
servers.cpp:25: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]
   25 |     for (i = 0 ; i < v[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
servers.cpp: In function 'int ok(int, int, int)':
servers.cpp:89: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]
   89 |                 for (j = 0 ; j < v[y].size() ; j++){
      |                              ~~^~~~~~~~~~~~~
servers.cpp:121: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]
  121 |                 for (j = 0 ; j < v[x].size() ; j++){
      |                              ~~^~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:164:58: warning: unused variable 'j' [-Wunused-variable]
  164 |     int n , q , cnt , i , x , y , mch = 0 , powe , fth , j , vecin;
      |                                                          ^
servers.cpp:164:62: warning: unused variable 'vecin' [-Wunused-variable]
  164 |     int n , q , cnt , i , x , y , mch = 0 , powe , fth , j , vecin;
      |                                                              ^~~~~
servers.cpp:252:10: warning: unused variable 'ans' [-Wunused-variable]
  252 |     char ans[10];
      |          ^~~
servers.cpp:166:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     fscanf (fin,"%d%d\n",&n,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:171:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |             fscanf (fin,"%d%d\n",&x,&y);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:179:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |             fscanf (fin,"%d%d\n",&x,&y);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 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: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5