Submission #1082417

#TimeUsernameProblemLanguageResultExecution timeMemory
1082417nikdThe Ties That Guide Us (CEOI23_incursion)C++17
0 / 100
80 ms9304 KiB
#include <vector> #include "incursion.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> adj1; vector<int> siz; vector<int> marked; int n; void calcsiz(int v, int e){ siz[v]=1; for(int u: adj1[v]){ if(u==e) continue; calcsiz(u, v); siz[v]+=siz[u]; } return; } void dfsmark(int v, int e){ int f1, f2; f1 = f2 = -1; for(int u: adj1[v]){ if(u==e) continue; if(f1!=-1) f2 = u; else f1 = u; dfsmark(u, v); } int var = n- (f1!=-1 ? siz[f1] : 0) - (f2!=-1 ? siz[f2] : 0)-1; if(f1!=-1 && siz[f1]>=var){ marked[v]=0; } if(f2!=-1 && siz[f2]>=var){ marked[v]=0; } return; } vector<int> mark(vector<pair<int, int>> F, int safe) { n = F.size()+1; safe--; adj1.resize(n); for(int i = 0; i<n-1; i++){ if(F[i].first == 0 || F[i].second == 0) while(1); } for(int i = 0; i<n-1; i++){ adj1[F[i].first-1].push_back(F[i].second-1); adj1[F[i].second-1].push_back(F[i].first-1); } siz.resize(n); calcsiz(safe, safe); marked.resize(n, 1); marked[safe]=0; for(int u: adj1[safe]){ dfsmark(u, safe); } return marked; } vector<vector<pair<int, int>>> adj2; vector<int> vis; void calcsiz2(int v, int e){ siz[v]=1; for(auto eg: adj2[v]){ int u = eg.first; if(u==e) continue; calcsiz2(u, v); siz[v]+=siz[u]; } return; } void calcsiz3(int v, int e){ int var = 0; for(auto& eg: adj2[v]){ int u = eg.first; if(u==e){ continue; } calcsiz3(u, v); eg.second = siz[u]; var += siz[u]; } for(auto& eg: adj2[v]){ int u = eg.first; if(u==e){ eg.second = n-var-1; } } return; } int real_pos; int visit2(int v){ if(vis[v]==-1){ real_pos = v; return vis[v] = visit(v+1); } return vis[v]; } void locate(vector<pair<int, int>> F, int curr, int t) { adj2.resize(n); vis.resize(n, -1); for(int i = 0; i<n-1; i++){ adj2[F[i].first-1].push_back({F[i].second-1, -1}); adj2[F[i].second-1].push_back({F[i].first-1, -1}); } curr--; calcsiz2(curr, curr); calcsiz3(curr, curr); int v = curr; real_pos = v; vis[curr]=t; while(1){ sort(adj2[v].begin(), adj2[v].end(), [](auto a, auto b){ return a.second > b.second; }); if(t){ v = adj2[v][0].first; t = visit2(v); } else{ if(adj2[v].size()<2) return; if(adj2[v][0].second==adj2[v][1].second){ t = visit2(adj2[v][0].first); if(t==1){ t = visit2(v); if(real_pos!=v){ visit(v+1); real_pos = v; } if(adj2[v].size()<2) return; t = visit2(adj2[v][1].first); if(t==1){ t = visit2(v); if(real_pos!=v){ visit(v+1); real_pos = v; } if(adj2[v].size()<3) return; t = visit2(adj2[v][2].first); if(t==1){ visit2(v); if(real_pos!=v){ visit(v+1); real_pos = v; } return; } else v = adj2[v][2].first; } else v = adj2[v][1].first; } else v = adj2[v][0].first; } else{ t = visit2(adj2[v][1].first); if(t==1){ t = visit2(v); if(real_pos!=v){ visit(v+1); real_pos = v; } if(adj2[v].size()<3) return; t = visit2(adj2[v][2].first); if(t==1){ visit2(v); if(real_pos!=v){ visit(v+1); real_pos = v; } return; } else v = adj2[v][2].first; } else v = adj2[v][1].first; } } } }

Compilation message (stderr)

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 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...