oj.uz

Submission #1065086

# Submission time Handle Problem Language Result Execution time Memory
1065086 2024-08-18T22:28:02 Z beaconmc The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 284 ms 15888 KB 
#include "incursion.h"

#include <bits/stdc++.h>
 
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;



ll sub[50000];
vector<ll> edges[50000];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];
ll n;



void dfs(ll a, ll p, ll d){
    depth[a] = d;
    par[a] = p;
    sub[a] = 1;
    for (auto&i : edges[a]){
        if (i != p) dfs(i,a,d+1), sub[a] += sub[i];
    }
}

ll centfind(ll a, ll p){
    visited[a] = 1;
    for (auto&i : edges[a]){
        if (i!=p && sub[i] > n/2) return centfind(i, a);
    }
    return a;
}





vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    n = (ll)F.size()+1;
    vector<int> ties(n);

    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0, visited[i] = 0;

    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(1, -1, 0);

    ll cent = centfind(1, -1);
    ll root = -1;
    for (auto&i : edges[cent]){
        if (i != par[cent]){
            root = i;
            dfs(root, -1, 0);
            break;
        }
    }
    ll cent2 = centfind(root, -1);


    dfs(cent, -1, 0);


    FOR(i,0,50000) visited[i] = 0;

    while (safe != -1){
        ties[safe-1] = 1;
        if (safe==cent || safe==cent2) break;
        safe = par[safe];
    }

    return ties;


}

bool cmp(ll a, ll b){
    return sub[a] < sub[b];
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
    n = (ll)F.size()+1;

    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0, visited[i] = 0;

    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(1, -1, 0);

    ll cent = centfind(1, -1);
    ll root = -1;
    FOR(i,1,n+1){
        if (!visited[i]){
            root = i;
            dfs(root, -1, 0);
            break;
        }
    }
    ll cent2 = centfind(root, -1);


    dfs(cent, -1, 0);
    FOR(i,0,50000) visited[i] = 0;
    visited[curr] = 1;

    //cout << cent << endl;

    while (t != 1 && curr != cent){
        t = visit(par[curr]);
        curr = par[curr];
        visited[curr] = 1;
    }
    if (t != 1){
        t = visit(cent2);
        curr = cent2;
        visited[curr] = 1;
    }

    while (1){
        //cout << curr << endl;

        visited[curr] = 1;
        if (t==0 && curr!=cent){
            t = visit(par[curr]);
            curr = par[curr];
            continue;
        }
        sort(edges[curr].begin(), edges[curr].end(), cmp);
        reverse(edges[curr].begin(), edges[curr].end());
        bool done = false;


        for (auto&i : edges[curr]){

            if (i==par[curr]) continue;

            if (!visited[i]){
                visited[i] = true;
                t = visit(i);
                curr = i;
                done = true;
                break;
            }
        }

        if (!done){
            return;
        }


    }



}

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 4608 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 14832 KB Correct
2 Correct 213 ms 14564 KB Correct
3 Correct 124 ms 14424 KB Correct
4 Correct 123 ms 15200 KB Correct
5 Correct 197 ms 15012 KB Correct
6 Correct 89 ms 15084 KB Correct
7 Correct 96 ms 13568 KB Correct
8 Correct 224 ms 15104 KB Correct
9 Correct 216 ms 14848 KB Correct
10 Correct 161 ms 14744 KB Correct
11 Correct 107 ms 15340 KB Correct
12 Correct 265 ms 13788 KB Correct
13 Correct 90 ms 14180 KB Correct
14 Correct 90 ms 14180 KB Correct
15 Correct 207 ms 14844 KB Correct
16 Correct 219 ms 15888 KB Correct
17 Correct 130 ms 13212 KB Correct
18 Correct 87 ms 15188 KB Correct
19 Correct 177 ms 14060 KB Correct
20 Correct 89 ms 15108 KB Correct
21 Correct 80 ms 13828 KB Correct
22 Correct 207 ms 14668 KB Correct
23 Correct 214 ms 14336 KB Correct
24 Correct 96 ms 13920 KB Correct
25 Correct 101 ms 15228 KB Correct
26 Correct 92 ms 14592 KB Correct
27 Correct 79 ms 13736 KB Correct
28 Correct 98 ms 15604 KB Correct
29 Correct 209 ms 14160 KB Correct
30 Correct 243 ms 14592 KB Correct
31 Correct 87 ms 15192 KB Correct
32 Correct 284 ms 14776 KB Correct
33 Correct 234 ms 14236 KB Correct
34 Correct 91 ms 14456 KB Correct
35 Correct 81 ms 13728 KB Correct
36 Correct 228 ms 14688 KB Correct
37 Correct 215 ms 14284 KB Correct
38 Correct 264 ms 14956 KB Correct
39 Correct 160 ms 15260 KB Correct
40 Incorrect 93 ms 15060 KB Not correct
41 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9116 KB Correct
2 Correct 81 ms 9284 KB Correct
3 Correct 72 ms 9044 KB Correct
4 Correct 106 ms 12256 KB Correct
5 Correct 143 ms 11496 KB Correct
6 Correct 155 ms 11540 KB Correct
7 Correct 78 ms 9116 KB Correct
8 Correct 82 ms 8964 KB Correct
9 Correct 79 ms 8860 KB Correct
10 Correct 78 ms 8968 KB Correct
11 Correct 80 ms 8864 KB Correct
12 Correct 73 ms 8776 KB Correct
13 Correct 78 ms 8956 KB Correct
14 Correct 52 ms 7596 KB Correct
15 Correct 61 ms 7856 KB Correct
16 Correct 70 ms 8948 KB Correct
17 Correct 75 ms 8700 KB Correct
18 Correct 80 ms 9020 KB Correct
19 Correct 75 ms 8940 KB Correct
20 Correct 61 ms 7836 KB Correct
21 Correct 60 ms 7612 KB Correct
22 Correct 53 ms 8112 KB Correct
23 Correct 62 ms 7824 KB Correct
24 Correct 61 ms 7840 KB Correct
25 Correct 61 ms 7816 KB Correct
26 Correct 81 ms 9116 KB Correct
27 Correct 84 ms 8860 KB Correct
28 Correct 78 ms 8956 KB Correct
29 Correct 75 ms 8892 KB Correct
30 Correct 86 ms 9360 KB Correct
31 Correct 81 ms 8956 KB Correct
32 Correct 76 ms 9196 KB Correct
33 Correct 72 ms 8860 KB Correct
34 Correct 80 ms 8960 KB Correct
35 Correct 86 ms 8948 KB Correct
36 Correct 78 ms 9124 KB Correct
37 Correct 77 ms 8868 KB Correct
38 Correct 79 ms 8956 KB Correct
39 Correct 86 ms 9020 KB Correct
40 Correct 90 ms 8848 KB Correct
41 Correct 82 ms 8964 KB Correct
42 Correct 83 ms 8872 KB Correct
43 Correct 68 ms 9048 KB Correct
44 Correct 77 ms 9196 KB Correct
45 Correct 77 ms 8860 KB Correct
46 Correct 81 ms 9216 KB Correct
47 Correct 78 ms 9076 KB Correct
48 Correct 78 ms 9044 KB Correct
49 Correct 80 ms 8976 KB Correct
50 Correct 71 ms 8928 KB Correct
51 Correct 82 ms 8948 KB Correct
52 Correct 84 ms 9060 KB Correct
53 Correct 79 ms 8952 KB Correct
54 Correct 80 ms 9200 KB Correct
55 Correct 88 ms 8700 KB Correct
56 Correct 79 ms 9116 KB Correct
57 Correct 78 ms 9120 KB Correct
58 Correct 79 ms 9116 KB Correct
59 Correct 76 ms 9128 KB Correct
60 Correct 78 ms 9120 KB Correct
61 Correct 72 ms 9204 KB Correct
62 Correct 69 ms 9376 KB Correct
63 Correct 87 ms 9204 KB Correct
64 Correct 79 ms 9208 KB Correct
65 Correct 79 ms 9372 KB Correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4608 KB Correct
2 Correct 216 ms 14832 KB Correct
3 Correct 213 ms 14564 KB Correct
4 Correct 124 ms 14424 KB Correct
5 Correct 123 ms 15200 KB Correct
6 Correct 197 ms 15012 KB Correct
7 Correct 89 ms 15084 KB Correct
8 Correct 96 ms 13568 KB Correct
9 Correct 224 ms 15104 KB Correct
10 Correct 216 ms 14848 KB Correct
11 Correct 161 ms 14744 KB Correct
12 Correct 107 ms 15340 KB Correct
13 Correct 265 ms 13788 KB Correct
14 Correct 90 ms 14180 KB Correct
15 Correct 90 ms 14180 KB Correct
16 Correct 207 ms 14844 KB Correct
17 Correct 219 ms 15888 KB Correct
18 Correct 130 ms 13212 KB Correct
19 Correct 87 ms 15188 KB Correct
20 Correct 177 ms 14060 KB Correct
21 Correct 89 ms 15108 KB Correct
22 Correct 80 ms 13828 KB Correct
23 Correct 207 ms 14668 KB Correct
24 Correct 214 ms 14336 KB Correct
25 Correct 96 ms 13920 KB Correct
26 Correct 101 ms 15228 KB Correct
27 Correct 92 ms 14592 KB Correct
28 Correct 79 ms 13736 KB Correct
29 Correct 98 ms 15604 KB Correct
30 Correct 209 ms 14160 KB Correct
31 Correct 243 ms 14592 KB Correct
32 Correct 87 ms 15192 KB Correct
33 Correct 284 ms 14776 KB Correct
34 Correct 234 ms 14236 KB Correct
35 Correct 91 ms 14456 KB Correct
36 Correct 81 ms 13728 KB Correct
37 Correct 228 ms 14688 KB Correct
38 Correct 215 ms 14284 KB Correct
39 Correct 264 ms 14956 KB Correct
40 Correct 160 ms 15260 KB Correct
41 Incorrect 93 ms 15060 KB Not correct
42 Halted 0 ms 0 KB -