제출 #612601

#제출 시각아이디문제언어결과실행 시간메모리
612601AugustinasJucas즐거운 행로 (APIO20_fun)C++14
21 / 100
135 ms24308 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; const int dydis = 1e5 + 10; vector<int> gr[dydis]; int n; bool rem[dydis] = {}; int dst[dydis] = {}; void dfs(int v, int came) { if(rem[v]) return; for(auto x : gr[v]) { if(x == came) continue; dst[x] = dst[v] + 1; ////cout << "dst[" << v << "] = " << dst[v] << ", tai dst[" << x << "] = " << dst[x] << endl; dfs(x, v); } } int furthest (int a) { // //cout << "ieskau atstumu nuo " << a << endl; dst[a] = 0; dfs(a, -1); int mx = 0; int sk = a; for(int i = 0; i < n; i++) { if(rem[i]) continue; // //cout << "dst[" << i << "] = " << dst[i] << endl; if(dst[i] > mx) { mx = dst[i]; sk = i; } } return sk; } vector<int> nMazas(){ for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { if(hoursRequired(i, j) == 1) { gr[i].push_back(j); gr[j].push_back(i); } } } vector<int> ret; int v = furthest(0); for(int i = 0; i < n; i++) { // //cout << "i = " << i << ", v = " << v << endl; ret.push_back(v); int was = v; v = furthest(v); rem[was] = 1; // //cout << endl; } return ret; } pair<int, int> toliausia[dydis]; void d(int v, int came) { if(rem[v]) return ; toliausia[v] = {-1, v}; for(auto x : gr[v]) { if(x == came) continue; d(x, v); toliausia[v] = max(toliausia[v], toliausia[x]); } toliausia[v].first++; } void remN(int v){ int in = v; while(!rem[v]) { toliausia[v] = {0, v}; if(v == in) toliausia[v] = {-1, -1}; for(auto x : gr[v]) { if(x < v) continue; if(rem[x]) continue; toliausia[v] = max(toliausia[v], make_pair(toliausia[x].first+1, toliausia[x].second)); } if(v == 0) break ; v = (v - 1) / 2; } rem[in] = 1; //cout << "isemus " << in << ", toliausios: \n"; for(int i = 0; i < n; i++) { //cout << i << "-ajai toliausia yra " << toliausia[i].second << ", ds = "<< toliausia[i].first << endl; } } int findFar(int v) { pair<int, int> ret = toliausia[v]; int init = v; int ds = 1; int V = v; //cout << "findfar nuo " << v << endl; while(true) { for(auto x : gr[v]) { if(x == init || x < v) continue; if(rem[x]) continue; //cout << "v = " << v << ", x = " << x <<", tai dst gali buti " << toliausia[x].first + ds<< endl; ret = max(ret, make_pair(toliausia[x].first + ds, toliausia[x].second)); } if(rem[v] || v == 0) break; init = v; v = (v - 1) / 2; ds++; } return ret.second; } vector<int> createFunTour(int N, int Q) { if(n <= 500) nMazas(); n = N; // //cout << "a" << endl; // if(n <= 500) return nMazas(); for(int i = 1; i < n; i++) { int pr = (i-1) / 2; gr[pr].push_back(i); gr[i].push_back(pr); } ////cout << "x" << endl; d(0, -1); // //cout << "don" << endl; int v = toliausia[0].second; set<int> nodes; for(int i = 0; i < n; i++) nodes.insert(i); vector<int> ret; int root = 0; for(int i = 0; i < n-2; i++) { int was = v; v = findFar(v); //cout << "toliausia nuo " << was << " yra " << v << endl; remN(was); ret.push_back(was); nodes.erase(was); } ret.push_back(*nodes.begin()); nodes.erase(*nodes.begin()); ret.push_back(*nodes.begin()); //cout << "ret: "; for(auto x : ret) //cout << x <<" "; //cout << endl; return ret; }

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

fun.cpp: In function 'int findFar(int)':
fun.cpp:99:9: warning: unused variable 'V' [-Wunused-variable]
   99 |     int V = v;
      |         ^
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:133:9: warning: unused variable 'root' [-Wunused-variable]
  133 |     int root = 0;
      |         ^~~~
#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...