oj.uz

Submission #1073080

# Submission time Handle Problem Language Result Execution time Memory
1073080 2024-08-24T09:18:45 Z vjudge1 The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 954 ms 16960 KB 
#include <vector>
#include "incursion.h"
#include <cstdio>

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

#define sz(x) ((int)(x).size())

using pii = pair<int, int>;
using tii = tuple<int, int, int>;



const int nmax = 45e3 + 5;

vector<int> g[nmax];

int area[nmax];
int father[nmax];
#define N uhasfuhafs
int N;

void initarea(int node, int f) {
   area[node] = 1;
   father[node] = f;
   for(auto x : g[node]) {
      if(x == f) continue;
      initarea(x, node);
      area[node] += area[x];
   }
   return;
}
pii findcentr(int node, int f) {
   cerr << node << ' ' << area[node] << '\n';
   for(auto x : g[node]) {
      if(x == f) continue;
      cerr << '\t' << x << ' ' << area[x] << '\n';
      if(area[x] * 2 == N) { return pii{node, x}; }
      if(area[x] * 2 > N) { return findcentr(x, node); }
   }
   return pii{node, node};
}

int make_graph(vector<pii> F) {
   for(auto &[a, b] : F) --a, --b;
   N = sz(F) + 1;
   for(int i = 0; i <= N + 1; i++) g[i].clear();
   
   for(auto [a, b] : F) {
      g[a].emplace_back(b);
      g[b].emplace_back(a);
   }
   initarea(0, 0);
   auto [u_, v_] = findcentr(0, 0);
   int root;
   
   if(u_ != v_) {
      for(int i = 0; i < sz(g[u_]); i++) {
         if(g[u_][i] == v_) {
            swap(g[u_][i], g[u_].back());
            g[u_].pop_back();
            break;
         }
      }
      for(int i = 0; i < sz(g[v_]); i++) {
         if(g[v_][i] == u_) {
            swap(g[v_][i], g[v_].back());
            g[v_].pop_back();
            break;
         }
      }
      g[u_].emplace_back(N);
      g[v_].emplace_back(N);
      g[N].emplace_back(u_);
      g[N].emplace_back(v_);
      N++;
      root = N - 1;
   }
   else { root = u_; }
   return root;
}

vector<int> known;

bool dfs(int node, int f, int where) {
   bool znayu = node == where;
   for(auto x : g[node]) {
      if(x == f) continue;
      znayu |= dfs(x, node, where);
   }
   known[node] = znayu;
   return known[node];
}

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
   --safe;
   int root = make_graph(F);
   known.resize(N);
   dfs(root, root, safe);
   cerr << root + 1 << '\n';
   known.resize(sz(F) + 1);
   return known;
}

int go(int x) {
   return visit(x +1);
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
   --curr;
   int root = make_graph(F);
   for(int i = 0; i< N; i++) {
      cerr << i << ": ";
      for(auto x : g[i]) cerr << x << ' ';
      cerr << '\n';
   }
   known.assign(N, -1);
   if(N != sz(F) + 1)
      known.back() = 1;
   initarea(root, root);
   
   while(1) {
      if(t == 0) {
         int u = father[curr];
         if(u == sz(F) + 1) {
            curr = g[u][0] ^ g[u][1] ^ curr;
            t = go(curr);
         }
         else {
            curr = father[curr];
            t = go(curr);
         }
      }
      else {
         int a = -1, b = -1;
         for(auto x : g[curr]) {
            if(x == father[curr]) continue;
            if(a == -1) a = x;
            else b = x;
         }
         
         //cerr << curr << ": " << a << ' ' << b << '\n';
         
         if(a == -1 && b == -1) return;
         if(b == -1) {
            int h = go(a);
            if(h == 1) {
               curr = a;
               t = 1;
               continue;
            }
            go(curr);
            return;
         }
         else {
            if(area[a] < area[b]) swap(a, b);
            int h = go(a);
            if(h == 1) {
               curr = a;
               t = 1;
               continue;
            }
            go(curr);
            h = go(b);
            if(h == 1) {
               curr = b;
               t = 1;
                continue;
            }
            go(curr);
            return;
         }
      }
   }
   
}

#undef N

Compilation message

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);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2820 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 14256 KB Correct
2 Correct 692 ms 14396 KB Correct
3 Correct 743 ms 15552 KB Correct
4 Correct 807 ms 16040 KB Correct
5 Correct 804 ms 16160 KB Correct
6 Correct 718 ms 16316 KB Correct
7 Correct 538 ms 14040 KB Correct
8 Correct 731 ms 14736 KB Correct
9 Correct 800 ms 15420 KB Correct
10 Correct 651 ms 14324 KB Correct
11 Correct 754 ms 16448 KB Correct
12 Correct 759 ms 14432 KB Correct
13 Correct 487 ms 13896 KB Correct
14 Correct 549 ms 14400 KB Correct
15 Correct 806 ms 15148 KB Correct
16 Correct 954 ms 16960 KB Correct
17 Correct 489 ms 13372 KB Correct
18 Correct 521 ms 13892 KB Correct
19 Correct 523 ms 13288 KB Correct
20 Correct 675 ms 16000 KB Correct
21 Correct 559 ms 14560 KB Correct
22 Correct 716 ms 14612 KB Correct
23 Correct 733 ms 14656 KB Correct
24 Correct 595 ms 14096 KB Correct
25 Correct 649 ms 15192 KB Correct
26 Correct 495 ms 13528 KB Correct
27 Correct 537 ms 14120 KB Correct
28 Correct 588 ms 15088 KB Correct
29 Correct 737 ms 14916 KB Correct
30 Correct 647 ms 13668 KB Correct
31 Correct 772 ms 16352 KB Correct
32 Correct 812 ms 14912 KB Correct
33 Correct 851 ms 15548 KB Correct
34 Correct 518 ms 13888 KB Correct
35 Correct 434 ms 13212 KB Correct
36 Correct 729 ms 14788 KB Correct
37 Correct 744 ms 14928 KB Correct
38 Correct 870 ms 16060 KB Correct
39 Correct 803 ms 16224 KB Correct
40 Correct 760 ms 15596 KB Correct
41 Correct 696 ms 15168 KB Correct
42 Correct 639 ms 14844 KB Correct
43 Correct 796 ms 15076 KB Correct
44 Correct 647 ms 13084 KB Correct
45 Correct 588 ms 13896 KB Correct
46 Correct 576 ms 14328 KB Correct
47 Correct 734 ms 15580 KB Correct
48 Correct 518 ms 13200 KB Correct
49 Correct 715 ms 15908 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 9144 KB Correct
2 Correct 479 ms 9364 KB Correct
3 Correct 521 ms 9164 KB Correct
4 Correct 703 ms 12968 KB Correct
5 Incorrect 560 ms 11964 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2820 KB Correct
2 Correct 660 ms 14256 KB Correct
3 Correct 692 ms 14396 KB Correct
4 Correct 743 ms 15552 KB Correct
5 Correct 807 ms 16040 KB Correct
6 Correct 804 ms 16160 KB Correct
7 Correct 718 ms 16316 KB Correct
8 Correct 538 ms 14040 KB Correct
9 Correct 731 ms 14736 KB Correct
10 Correct 800 ms 15420 KB Correct
11 Correct 651 ms 14324 KB Correct
12 Correct 754 ms 16448 KB Correct
13 Correct 759 ms 14432 KB Correct
14 Correct 487 ms 13896 KB Correct
15 Correct 549 ms 14400 KB Correct
16 Correct 806 ms 15148 KB Correct
17 Correct 954 ms 16960 KB Correct
18 Correct 489 ms 13372 KB Correct
19 Correct 521 ms 13892 KB Correct
20 Correct 523 ms 13288 KB Correct
21 Correct 675 ms 16000 KB Correct
22 Correct 559 ms 14560 KB Correct
23 Correct 716 ms 14612 KB Correct
24 Correct 733 ms 14656 KB Correct
25 Correct 595 ms 14096 KB Correct
26 Correct 649 ms 15192 KB Correct
27 Correct 495 ms 13528 KB Correct
28 Correct 537 ms 14120 KB Correct
29 Correct 588 ms 15088 KB Correct
30 Correct 737 ms 14916 KB Correct
31 Correct 647 ms 13668 KB Correct
32 Correct 772 ms 16352 KB Correct
33 Correct 812 ms 14912 KB Correct
34 Correct 851 ms 15548 KB Correct
35 Correct 518 ms 13888 KB Correct
36 Correct 434 ms 13212 KB Correct
37 Correct 729 ms 14788 KB Correct
38 Correct 744 ms 14928 KB Correct
39 Correct 870 ms 16060 KB Correct
40 Correct 803 ms 16224 KB Correct
41 Correct 760 ms 15596 KB Correct
42 Correct 696 ms 15168 KB Correct
43 Correct 639 ms 14844 KB Correct
44 Correct 796 ms 15076 KB Correct
45 Correct 647 ms 13084 KB Correct
46 Correct 588 ms 13896 KB Correct
47 Correct 576 ms 14328 KB Correct
48 Correct 734 ms 15580 KB Correct
49 Correct 518 ms 13200 KB Correct
50 Correct 715 ms 15908 KB Correct
51 Correct 455 ms 9144 KB Correct
52 Correct 479 ms 9364 KB Correct
53 Correct 521 ms 9164 KB Correct
54 Correct 703 ms 12968 KB Correct
55 Incorrect 560 ms 11964 KB Not correct
56 Halted 0 ms 0 KB -