제출 #185429

#제출 시각아이디문제언어결과실행 시간메모리
185429alexandra_udristoiu늑대인간 (IOI18_werewolf)C++14
34 / 100
818 ms524288 KiB
#include<fstream> #include<vector> #include<algorithm> #include<cstring> #include "werewolf.h" #define DIM 200005 #define f first #define s second using namespace std; static int n, q, nr; static int t[DIM], aint[4 * DIM], d[DIM]; static pair<int, int> p[2][DIM]; static vector<int> v[DIM], vt[2][DIM], sol; struct str{ int ind, x, y, st, dr, p1, u1, p2, u2; }; static str w[DIM]; int cmp1(str a, str b){ return a.st > b.st; } int cmp2(str a, str b){ return a.dr < b.dr; } int cmp3(str a, str b){ return a.p1 > b.p1; } int rad(int x){ int y, aux; y = x; while(t[y] != 0){ y = t[y]; } while(t[x] != 0){ aux = t[x]; t[x] = y; x = aux; } return y; } void update(int nod, int st, int dr, int p, int val){ if(st == dr){ aint[nod] = val; } else{ int mid = (st + dr) / 2; if(p <= mid){ update(2 * nod, st, mid, p, val); } else{ update(2 * nod + 1, mid + 1, dr, p, val); } aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]); } } int query(int nod, int st, int dr, int p, int u){ if(p <= st && dr <= u){ return aint[nod]; } else{ int mid = (st + dr) / 2; int x, y; x = y = n + 1; if(p <= mid){ x = query(2 * nod, st, mid, p, u); } if(u > mid){ y = query(2 * nod + 1, mid + 1, dr, p, u); } return min(x, y); } } void dfs(int nod, int ind){ p[ind][nod].f = ++nr; for(int i = 0; i < vt[ind][nod].size(); i++){ dfs(vt[ind][nod][i], ind); } p[ind][nod].s = nr; } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { int i, j, nod, u, r; n = N; q = S.size(); sol.resize(q); for(i = 0; i < n - 1; i++){ X[i]++; Y[i]++; v[ X[i] ].push_back(Y[i]); v[ Y[i] ].push_back(X[i]); } for(i = 0; i < q; i++){ w[i + 1] = {i, S[i] + 1, E[i] + 1, L[i] + 1, R[i] + 1, 0, 0, 0, 0}; } sort(w + 1, w + q + 1, cmp1); u = 1; for(i = n; i >= 1; i--){ for(j = 0; j < v[i].size(); j++){ nod = v[i][j]; r = rad(nod); if(nod > i && r != i){ t[r] = i; vt[0][i].push_back(r); } } while(w[u].st == i){ w[u].p1 = rad(w[u].x); u++; } } memset(t, 0, sizeof(t) ); sort(w + 1, w + q + 1, cmp2); u = 1; for(i = 1; i <= n; i++){ for(j = 0; j < v[i].size(); j++){ nod = v[i][j]; r = rad(nod); if(nod < i && r != i){ t[r] = i; vt[1][i].push_back(r); } } while(w[u].dr == i){ w[u].p2 = rad(w[u].y); u++; } } dfs(1, 0); nr = 0; dfs(n, 1); for(i = 1; i <= n; i++){ d[ p[0][i].f ] = i; } for(i = 1; i <= q; i++){ nod = w[i].p1; w[i].p1 = p[0][nod].f; w[i].u1 = p[0][nod].s; nod = w[i].p2; w[i].p2 = p[1][nod].f; w[i].u2 = p[1][nod].s; } sort(w + 1, w + q + 1, cmp3); u = 1; for(i = 1; i <= 4 * n; i++){ aint[i] = n + 1; } for(i = n; i >= 1; i--){ update(1, 1, n, p[1][ d[i] ].f, i); while(w[u].p1 == i){ if( query(1, 1, n, w[u].p2, w[u].u2) <= w[u].u1){ sol[ w[u].ind ] = 1; } else{ sol[ w[u].ind ] = 0; } u++; } } return sol; }

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

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vt[ind][nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[i].size(); j++){
                    ~~^~~~~~~~~~~~~
werewolf.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[i].size(); j++){
                    ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...