oj.uz

Submission #1065012

# Submission time Handle Problem Language Result Execution time Memory
1065012 2024-08-18T21:18:59 Z beaconmc The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 277 ms 15524 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){
    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;

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

    dfs(cent, -1, 0);


    while (safe != -1){
        ties[safe-1] = 1;
        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;

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

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

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

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

        }
        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){
            if (curr != cent && visited[par[curr]] == 0){
                t = visit(par[curr]);
                visited[par[curr]] = 1;
                curr = par[curr];
            }else{
                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 4364 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 13272 KB Correct
2 Correct 207 ms 13764 KB Correct
3 Correct 137 ms 14464 KB Correct
4 Correct 106 ms 14844 KB Correct
5 Correct 223 ms 14848 KB Correct
6 Correct 81 ms 14688 KB Correct
7 Correct 83 ms 13480 KB Correct
8 Correct 223 ms 13932 KB Correct
9 Correct 216 ms 14456 KB Correct
10 Correct 173 ms 13764 KB Correct
11 Correct 104 ms 15184 KB Correct
12 Correct 277 ms 13688 KB Correct
13 Correct 94 ms 13136 KB Correct
14 Correct 84 ms 13724 KB Correct
15 Correct 233 ms 14268 KB Correct
16 Correct 205 ms 15524 KB Correct
17 Correct 120 ms 12844 KB Correct
18 Incorrect 90 ms 13052 KB Not correct
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 8960 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4364 KB Correct
2 Correct 219 ms 13272 KB Correct
3 Correct 207 ms 13764 KB Correct
4 Correct 137 ms 14464 KB Correct
5 Correct 106 ms 14844 KB Correct
6 Correct 223 ms 14848 KB Correct
7 Correct 81 ms 14688 KB Correct
8 Correct 83 ms 13480 KB Correct
9 Correct 223 ms 13932 KB Correct
10 Correct 216 ms 14456 KB Correct
11 Correct 173 ms 13764 KB Correct
12 Correct 104 ms 15184 KB Correct
13 Correct 277 ms 13688 KB Correct
14 Correct 94 ms 13136 KB Correct
15 Correct 84 ms 13724 KB Correct
16 Correct 233 ms 14268 KB Correct
17 Correct 205 ms 15524 KB Correct
18 Correct 120 ms 12844 KB Correct
19 Incorrect 90 ms 13052 KB Not correct
20 Halted 0 ms 0 KB -