Submission #1070593

#TimeUsernameProblemLanguageResultExecution timeMemory
1070593GrindMachineThe Ties That Guide Us (CEOI23_incursion)C++17
100 / 100
308 ms10844 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif /* read the edi a long time ago, dont really remember much from there */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "incursion.h" std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) { // return {2, 2, 0}; int n = sz(F)+1; vector<vector<int>> adj(n+5); for(auto [u,v] : F){ adj[u].pb(v), adj[v].pb(u); } vector<int> par(n+5), subsiz(n+5); auto dfs = [&](int u, int p, auto &&dfs) -> void{ par[u] = p; subsiz[u] = 1; trav(v,adj[u]){ if(v == p) conts; dfs(v,u,dfs); subsiz[u] += subsiz[v]; } }; dfs(1,-1,dfs); vector<int> centroids; rep1(u,n){ bool ok = true; trav(v,adj[u]){ int s = subsiz[v]; if(v == par[u]){ s = n-subsiz[u]; } if(s > n/2){ ok = false; } } if(ok){ centroids.pb(u); } } int siz = sz(centroids); assert(siz >= 1 and siz <= 2); auto can_reach = [&](int u, int p, auto &&can_reach) -> bool{ bool ok = false; if(u == safe) ok = true; trav(v,adj[u]){ if(v == p) conts; if(count(all(centroids),v)) conts; ok |= can_reach(v,u,can_reach); } return ok; }; int r = -1; if(siz == 1){ r = centroids[0]; } else{ rep(j,2){ if(can_reach(centroids[j],-1,can_reach)){ assert(r == -1); r = centroids[j]; } } } assert(r != -1); dfs(r,-1,dfs); vector<int> ans(n); while(safe != -1){ ans[safe-1] = 1; safe = par[safe]; } return ans; } void locate(std::vector<std::pair<int, int>> F, int curr, int cnt) { int n = sz(F)+1; vector<vector<int>> adj(n+5); for(auto [u,v] : F){ adj[u].pb(v), adj[v].pb(u); } vector<int> par(n+5), subsiz(n+5); auto dfs = [&](int u, int p, auto &&dfs) -> void{ par[u] = p; subsiz[u] = 1; trav(v,adj[u]){ if(v == p) conts; dfs(v,u,dfs); subsiz[u] += subsiz[v]; } }; dfs(1,-1,dfs); vector<int> centroids; rep1(u,n){ bool ok = true; trav(v,adj[u]){ int s = subsiz[v]; if(v == par[u]){ s = n-subsiz[u]; } if(s > n/2){ ok = false; } } if(ok){ centroids.pb(u); } } int siz = sz(centroids); assert(siz >= 1 and siz <= 2); int r = centroids[0]; dfs(r,-1,dfs); if(siz == 1){ while(!cnt){ cnt = visit(par[curr]); curr = par[curr]; } while(true){ vector<pii> ord; trav(v,adj[curr]){ if(v == par[curr]) conts; ord.pb({subsiz[v],v}); } sort(rall(ord)); int nxt = -1; for(auto [s,v] : ord){ int x = visit(v); if(x){ nxt = v; break; } visit(curr); } if(nxt == -1) break; curr = nxt; } return; } while(!cnt){ if(curr == r){ curr = centroids[0]^centroids[1]^curr; visit(curr); break; } cnt = visit(par[curr]); curr = par[curr]; } while(true){ vector<pii> ord; trav(v,adj[curr]){ if(v == par[curr]) conts; ord.pb({subsiz[v],v}); } sort(rall(ord)); int nxt = -1; for(auto [s,v] : ord){ int x = visit(v); if(x){ nxt = v; break; } visit(curr); } if(nxt == -1) break; curr = nxt; } // int x; // x = visit(3); // if (x != 2) { // return; // } // x = visit(1); // if (x != 0) { // return; // } // x = visit(3); // if (x != 2) { // return; // } // x = visit(2); // if (x != 2) { // return; // } // return; }

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...