제출 #962823

#제출 시각아이디문제언어결과실행 시간메모리
962823PoPularPlusPlus마상시합 토너먼트 (IOI12_tournament)C++17
0 / 100
203 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define pb(x) push_back(x) const int N = 100003 , L = 22; struct dsu { vector<int> p; vector<int> top; void init(int n){ p.resize(n + 1); top.resize(2*(n + 1)); for(int i = 0; i <= n; i++){ p[i] = i; top[i] = i; } } int get(int x){ return p[x] = (p[x] == x ? x : get(p[x])); } int get_parent(int x){ return top[x] = (top[x] == x ? x : get(top[x])); } void unio(int x , int y){ x = get(x); y = get(y); if(y > x)swap(x,y); p[y] = x; } void put_parent(int x , int y){ top[x] = y; } }; struct Fen { int siz; vector<int> tree; void init(int n){ siz = n; tree.assign(n + 5,0); } void set(int i, int val){ i++; while(i <= siz){ tree[i]+=val; i += (i & -i); } } int sum(int i){ i++; int ans = 0; while(i > 0){ ans += tree[i]; i -= (i & -i); } return ans; } }; vector<int> adj[2*N]; int up[2*N][L] , tin[2*N] , tout[2*N] , timer; void dfs(int node , int par){ //cout << node << ' ' << par << endl; tin[node] = timer++; up[node][0] = par; for(int i = 1; i < L; i++){ up[node][i] = up[up[node][i-1]][i-1]; } for(int i : adj[node]){ dfs(i , node); } tout[node] = timer++; } bool is_ancestor(int x, int y){ return tin[x] <= tin[y] && tout[x] >= tout[y]; } int find(int x , int y){ if(is_ancestor(x,y))return x; if(is_ancestor(y,x))return y; for(int i = L - 1; i >= 0; i--){ if(!is_ancestor(up[x][i] , y)){ x = up[x][i]; } } return up[x][0]; } int dis(int x , int y){ int ans = 0; for(int i = L - 1; i >= 0; i--){ if(!is_ancestor(up[x][i] , y)){ x = up[x][i]; ans += (1 << i); } } return ans; } int GetBestPosition(int n, int m, int r, int *arr, int *s,int *e){ Fen ft; ft.init(n + 1); for(int i = 0; i < n; i++){ ft.set(i , 1); } int cur = n; dsu d; d.init(n + 1); for(int i = 0; i < m; i++){ int l = 0 , r = n-1; int ans = 0; while(l <= r){ int mid = (l + r)/2; int x = ft.sum(mid); if(x > s[i]){ r = mid - 1; } else if(x == s[i]){ ans = mid + 1; r = mid - 1; } else { l = mid + 1; } } vector<int> v; for(int pos = ans, cnt = s[i]; cnt <= e[i]; cnt++,pos++){ while(pos >= n){ ; } int last = d.get(pos); v.pb(last); pos = last; //cout << cnt << ' ' << s[i] << ' ' << e[i] << '\n'; } //cout << '\n'; for(int it : v){ //cout << it << ' '; adj[cur].pb(d.get_parent(it)); d.put_parent(d.get_parent(it) , cur); } //cout << '\n'; cur++; for(int j = 0; j < v.size() - 1; j++){ d.unio(v[j] , v[j+1]); ft.set(v[j] , 0); } } vector<int> better; for(int i = 0; i < n - 1; i++){ if(arr[i] > r){ better.pb(i); } } timer = 0; dfs(cur - 1 , cur-1); int j = 0; int res = 0; for(int i = 0; i < n; i++){ while(j < better.size() && better[j] < i){ j++; } int lca = cur - 1; if(j > 0){ int tp = find(better[j-1] , i); if(is_ancestor(lca , tp)){ lca = tp; } } if(j < better.size()){ int tp = find(better[j] + 1, i); if(is_ancestor(lca,tp)){ lca = tp; } } res = max(res , dis(i , lca)); } //cout << res << endl; return res; }

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

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:156:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |   for(int j = 0; j < v.size() - 1; j++){
      |                  ~~^~~~~~~~~~~~~~
tournament.cpp:175:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |   while(j < better.size() && better[j] < i){
      |         ~~^~~~~~~~~~~~~~~
tournament.cpp:185:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |   if(j < better.size()){
      |      ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...