oj.uz

Submission #1064742

# Submission time Handle Problem Language Result Execution time Memory
1064742 2024-08-18T17:19:13 Z beaconmc The Ties That Guide Us (CEOI23_incursion) C++17
12 / 100
 337 ms 39848 KB 
#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
 
typedef long long 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 ancc[50000][30];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];

ll anc(ll a, ll x){
    if (a==1) return 1;
    if (x==0) return par[a];
    if (ancc[a][x] != -1) return ancc[a][x];
    return ancc[a][x] = anc(anc(a,x-1),x-1);
}

ll lca(ll a, ll b){
    if (depth[a] < depth[b]) swap(a,b);
    FORNEG(i,29,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
    if (a==b) return a;
    FORNEG(i,29,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
    return par[a];
}

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];
    }
}


vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    vector<int> ties(F.size()+1);
    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
    FOR(i,0,50000) FOR(j,0,30) ancc[i][j] = -1;
    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(1, -1, 0);
    ll n = F.size()+1;
    FOR(i,1,n+1){
        if (safe == i){
            ties[i-1] = 2;
            continue;
        }
        vector<ll> idk;
        for (auto&k : edges[i]){
            if (k==par[i])idk.push_back(n-sub[i]);
            else idk.push_back(sub[k]);
        }

        sort(idk.begin(), idk.end());

        ll nxt = -1;
        ll sz = 0;
        for (auto&k : edges[i]){
            if (k != par[i] && lca(k, safe) == k) nxt = k;
        }
        if (nxt==-1) nxt = par[i];
        if (nxt == par[i]) sz = n-sub[i];
        else sz = sub[nxt];

        if (sz == idk[idk.size()-1]){
            ties[i-1] = 1;
        }else{
            ties[i-1] = 0;
        }
    }
    return ties;


}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {

    FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0, visited[i] = 0, unsure[i] = 0;
    FOR(i,0,50000) FOR(j,0,30) ancc[i][j] = -1;
    for (auto&i : F){
        edges[i.first].push_back(i.second);
        edges[i.second].push_back(i.first);
    }
    dfs(1, -1, 0);
    ll n = F.size()+1;
    ll here = t;
    while(here != 2){
        visited[curr] += 1;
        vector<vector<ll>> idk;
        for (auto&k : edges[curr]){
            if (par[curr] == k)idk.push_back({n-sub[curr], par[curr]});
            else idk.push_back({sub[k], k});
        }

        sort(idk.begin(), idk.end());


        if (idk.size()==2 && idk[0][0]==idk[1][0]) unsure[curr] = 1;
        if (idk.size()==3){
            if (here==1 && idk[2][0]==idk[1][0]) unsure[curr] =1;
            if (here==0 && idk[2][0]!=idk[1][0]) unsure[curr] = 1;
        }





        if (here==0){
            if (visited[idk[0][1]] && !unsure[idk[0][1]]) curr = idk[1][1], here = visit(curr);
            else curr = idk[0][1], here = visit(curr);
        }else{
             if (visited[idk[idk.size()-1][1]] && !unsure[idk[idk.size()-1][1]]) curr = idk[idk.size()-2][1], here = visit(curr);
             else curr = idk[idk.size()-1][1], here = visit(curr);
        }
    }
    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 Partially correct 7 ms 30220 KB Partially correct

Subtask #1
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 237 ms 38340 KB Partially correct
2 Partially correct 282 ms 38692 KB Partially correct
3 Partially correct 149 ms 39096 KB Partially correct
4 Partially correct 135 ms 39580 KB Partially correct
5 Partially correct 236 ms 39448 KB Partially correct
6 Partially correct 125 ms 39848 KB Partially correct
7 Partially correct 122 ms 38304 KB Partially correct
8 Partially correct 260 ms 38560 KB Partially correct
9 Partially correct 251 ms 39132 KB Partially correct
10 Partially correct 189 ms 38596 KB Partially correct
11 Partially correct 163 ms 39068 KB Partially correct
12 Partially correct 315 ms 37852 KB Partially correct
13 Partially correct 125 ms 38252 KB Partially correct
14 Partially correct 125 ms 37724 KB Partially correct
15 Partially correct 285 ms 38580 KB Partially correct
16 Partially correct 266 ms 39520 KB Partially correct
17 Partially correct 231 ms 37304 KB Partially correct
18 Partially correct 134 ms 38468 KB Partially correct
19 Partially correct 188 ms 37828 KB Partially correct
20 Partially correct 142 ms 39464 KB Partially correct
21 Partially correct 137 ms 38700 KB Partially correct
22 Partially correct 313 ms 38700 KB Partially correct
23 Partially correct 299 ms 38080 KB Partially correct
24 Partially correct 146 ms 37684 KB Partially correct
25 Partially correct 150 ms 38464 KB Partially correct
26 Partially correct 150 ms 37636 KB Partially correct
27 Partially correct 165 ms 37760 KB Partially correct
28 Partially correct 128 ms 38240 KB Partially correct
29 Partially correct 263 ms 38944 KB Partially correct
30 Partially correct 316 ms 38116 KB Partially correct
31 Partially correct 177 ms 38884 KB Partially correct
32 Partially correct 281 ms 38932 KB Partially correct
33 Partially correct 296 ms 39208 KB Partially correct
34 Partially correct 145 ms 37612 KB Partially correct
35 Partially correct 137 ms 37860 KB Partially correct
36 Partially correct 261 ms 38844 KB Partially correct
37 Partially correct 264 ms 38316 KB Partially correct
38 Partially correct 337 ms 38748 KB Partially correct
39 Partially correct 188 ms 39104 KB Partially correct
40 Partially correct 243 ms 38764 KB Partially correct
41 Partially correct 140 ms 39236 KB Partially correct
42 Partially correct 134 ms 38996 KB Partially correct
43 Partially correct 245 ms 39024 KB Partially correct
44 Partially correct 263 ms 37728 KB Partially correct
45 Partially correct 141 ms 38304 KB Partially correct
46 Partially correct 119 ms 38648 KB Partially correct
47 Partially correct 151 ms 39076 KB Partially correct
48 Partially correct 118 ms 37800 KB Partially correct
49 Partially correct 115 ms 39284 KB Partially correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 109 ms 35492 KB Partially correct
2 Incorrect 107 ms 35892 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 30220 KB Partially correct
2 Partially correct 237 ms 38340 KB Partially correct
3 Partially correct 282 ms 38692 KB Partially correct
4 Partially correct 149 ms 39096 KB Partially correct
5 Partially correct 135 ms 39580 KB Partially correct
6 Partially correct 236 ms 39448 KB Partially correct
7 Partially correct 125 ms 39848 KB Partially correct
8 Partially correct 122 ms 38304 KB Partially correct
9 Partially correct 260 ms 38560 KB Partially correct
10 Partially correct 251 ms 39132 KB Partially correct
11 Partially correct 189 ms 38596 KB Partially correct
12 Partially correct 163 ms 39068 KB Partially correct
13 Partially correct 315 ms 37852 KB Partially correct
14 Partially correct 125 ms 38252 KB Partially correct
15 Partially correct 125 ms 37724 KB Partially correct
16 Partially correct 285 ms 38580 KB Partially correct
17 Partially correct 266 ms 39520 KB Partially correct
18 Partially correct 231 ms 37304 KB Partially correct
19 Partially correct 134 ms 38468 KB Partially correct
20 Partially correct 188 ms 37828 KB Partially correct
21 Partially correct 142 ms 39464 KB Partially correct
22 Partially correct 137 ms 38700 KB Partially correct
23 Partially correct 313 ms 38700 KB Partially correct
24 Partially correct 299 ms 38080 KB Partially correct
25 Partially correct 146 ms 37684 KB Partially correct
26 Partially correct 150 ms 38464 KB Partially correct
27 Partially correct 150 ms 37636 KB Partially correct
28 Partially correct 165 ms 37760 KB Partially correct
29 Partially correct 128 ms 38240 KB Partially correct
30 Partially correct 263 ms 38944 KB Partially correct
31 Partially correct 316 ms 38116 KB Partially correct
32 Partially correct 177 ms 38884 KB Partially correct
33 Partially correct 281 ms 38932 KB Partially correct
34 Partially correct 296 ms 39208 KB Partially correct
35 Partially correct 145 ms 37612 KB Partially correct
36 Partially correct 137 ms 37860 KB Partially correct
37 Partially correct 261 ms 38844 KB Partially correct
38 Partially correct 264 ms 38316 KB Partially correct
39 Partially correct 337 ms 38748 KB Partially correct
40 Partially correct 188 ms 39104 KB Partially correct
41 Partially correct 243 ms 38764 KB Partially correct
42 Partially correct 140 ms 39236 KB Partially correct
43 Partially correct 134 ms 38996 KB Partially correct
44 Partially correct 245 ms 39024 KB Partially correct
45 Partially correct 263 ms 37728 KB Partially correct
46 Partially correct 141 ms 38304 KB Partially correct
47 Partially correct 119 ms 38648 KB Partially correct
48 Partially correct 151 ms 39076 KB Partially correct
49 Partially correct 118 ms 37800 KB Partially correct
50 Partially correct 115 ms 39284 KB Partially correct
51 Partially correct 109 ms 35492 KB Partially correct
52 Incorrect 107 ms 35892 KB Not correct
53 Halted 0 ms 0 KB -