제출 #411163

#제출 시각아이디문제언어결과실행 시간메모리
411163Ruxandra985Inside information (BOI21_servers)C++14
50 / 100
482 ms76992 KiB
#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);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...