oj.uz

Submission #410764

# Submission time Handle Problem Language Result Execution time Memory
410764 2021-05-23T16:58:39 Z Ruxandra985 Inside information (BOI21_servers) C++14
30 / 100
 3500 ms 69060 KB 
#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];
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;
    }

    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?
    //char ans[10];

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

        //if (i == 20337)
          //  printf ("a");

        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;
}

Compilation message

servers.cpp: In function 'void dfs(int, int, int, int)':
servers.cpp:24: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]
   24 |     for (i = 0 ; i < v[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
servers.cpp: In function 'int ok(int, int, int)':
servers.cpp:88: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]
   88 |                 for (j = 0 ; j < v[y].size() ; j++){
      |                              ~~^~~~~~~~~~~~~
servers.cpp:120: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]
  120 |                 for (j = 0 ; j < v[x].size() ; j++){
      |                              ~~^~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:240: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]
  240 |                 for (j = 0 ; j < v[fth].size() ; j++){
      |                              ~~^~~~~~~~~~~~~~~
servers.cpp:258: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]
  258 |                 for (j = 0 ; j < v[fth].size() ; j++){
      |                              ~~^~~~~~~~~~~~~~~
servers.cpp:165:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |     fscanf (fin,"%d%d\n",&n,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:170:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |             fscanf (fin,"%d%d\n",&x,&y);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp:178:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |             fscanf (fin,"%d%d\n",&x,&y);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5060 KB Output is correct
2 Correct 53 ms 7644 KB Output is correct
3 Correct 97 ms 7748 KB Output is correct
4 Correct 60 ms 7808 KB Output is correct
5 Correct 81 ms 7972 KB Output is correct
6 Correct 174 ms 7684 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5060 KB Output is correct
2 Correct 53 ms 7644 KB Output is correct
3 Correct 97 ms 7748 KB Output is correct
4 Correct 60 ms 7808 KB Output is correct
5 Correct 81 ms 7972 KB Output is correct
6 Correct 174 ms 7684 KB Output is correct
7 Incorrect 38 ms 4912 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4992 KB Output is correct
2 Execution timed out 3579 ms 42104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4992 KB Output is correct
2 Execution timed out 3579 ms 42104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4952 KB Output is correct
2 Correct 201 ms 60888 KB Output is correct
3 Correct 220 ms 60864 KB Output is correct
4 Correct 313 ms 66016 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4952 KB Output is correct
2 Correct 201 ms 60888 KB Output is correct
3 Correct 220 ms 60864 KB Output is correct
4 Correct 313 ms 66016 KB Output is correct
5 Incorrect 39 ms 4896 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5000 KB Output is correct
2 Correct 207 ms 52300 KB Output is correct
3 Correct 217 ms 52960 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5000 KB Output is correct
2 Correct 207 ms 52300 KB Output is correct
3 Correct 217 ms 52960 KB Output is correct
4 Incorrect 47 ms 4984 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5036 KB Output is correct
2 Correct 200 ms 60844 KB Output is correct
3 Correct 220 ms 60876 KB Output is correct
4 Correct 325 ms 65924 KB Output is correct
5 Correct 44 ms 5896 KB Output is correct
6 Correct 206 ms 52228 KB Output is correct
7 Correct 210 ms 52848 KB Output is correct
8 Correct 330 ms 53208 KB Output is correct
9 Correct 271 ms 53260 KB Output is correct
10 Correct 571 ms 69060 KB Output is correct
11 Correct 721 ms 67336 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5036 KB Output is correct
2 Correct 200 ms 60844 KB Output is correct
3 Correct 220 ms 60876 KB Output is correct
4 Correct 325 ms 65924 KB Output is correct
5 Correct 44 ms 5896 KB Output is correct
6 Correct 206 ms 52228 KB Output is correct
7 Correct 210 ms 52848 KB Output is correct
8 Correct 330 ms 53208 KB Output is correct
9 Correct 271 ms 53260 KB Output is correct
10 Correct 571 ms 69060 KB Output is correct
11 Correct 721 ms 67336 KB Output is correct
12 Incorrect 38 ms 4908 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5004 KB Output is correct
2 Correct 53 ms 7652 KB Output is correct
3 Correct 93 ms 7748 KB Output is correct
4 Correct 63 ms 7772 KB Output is correct
5 Correct 80 ms 7984 KB Output is correct
6 Correct 179 ms 7592 KB Output is correct
7 Correct 45 ms 5936 KB Output is correct
8 Execution timed out 3580 ms 42180 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5004 KB Output is correct
2 Correct 53 ms 7652 KB Output is correct
3 Correct 93 ms 7748 KB Output is correct
4 Correct 63 ms 7772 KB Output is correct
5 Correct 80 ms 7984 KB Output is correct
6 Correct 179 ms 7592 KB Output is correct
7 Correct 45 ms 5936 KB Output is correct
8 Execution timed out 3580 ms 42180 KB Time limit exceeded
9 Halted 0 ms 0 KB -