oj.uz

Submission #1064802

# Submission time Handle Problem Language Result Execution time Memory
1064802 2024-08-18T17:55:25 Z beaconmc The Ties That Guide Us (CEOI23_incursion) C++17
12 / 100
 316 ms 39580 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]] && unsure[curr]) 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]]){
                if (visited[idk[idk.size()-2][1]] && !unsure[idk[idk.size()-2][1]])curr = idk[idk.size()-3][1], here = visit(curr);
                else 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 12 ms 29712 KB Partially correct

Subtask #1
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 286 ms 37732 KB Partially correct
2 Partially correct 276 ms 38044 KB Partially correct
3 Partially correct 148 ms 38504 KB Partially correct
4 Partially correct 152 ms 39068 KB Partially correct
5 Partially correct 259 ms 38936 KB Partially correct
6 Partially correct 132 ms 38772 KB Partially correct
7 Partially correct 128 ms 37732 KB Partially correct
8 Partially correct 259 ms 38160 KB Partially correct
9 Partially correct 266 ms 38700 KB Partially correct
10 Partially correct 222 ms 37908 KB Partially correct
11 Partially correct 140 ms 39072 KB Partially correct
12 Partially correct 312 ms 37996 KB Partially correct
13 Partially correct 129 ms 37480 KB Partially correct
14 Partially correct 133 ms 37924 KB Partially correct
15 Partially correct 253 ms 38408 KB Partially correct
16 Partially correct 255 ms 39580 KB Partially correct
17 Partially correct 190 ms 37324 KB Partially correct
18 Partially correct 137 ms 37752 KB Partially correct
19 Partially correct 200 ms 37460 KB Partially correct
20 Partially correct 127 ms 38700 KB Partially correct
21 Partially correct 128 ms 37732 KB Partially correct
22 Partially correct 269 ms 38044 KB Partially correct
23 Partially correct 291 ms 38288 KB Partially correct
24 Partially correct 147 ms 37744 KB Partially correct
25 Partially correct 128 ms 38256 KB Partially correct
26 Partially correct 130 ms 37540 KB Partially correct
27 Partially correct 133 ms 37592 KB Partially correct
28 Partially correct 127 ms 38240 KB Partially correct
29 Partially correct 268 ms 38356 KB Partially correct
30 Partially correct 264 ms 37552 KB Partially correct
31 Partially correct 135 ms 39028 KB Partially correct
32 Partially correct 277 ms 38048 KB Partially correct
33 Partially correct 258 ms 38568 KB Partially correct
34 Partially correct 134 ms 37400 KB Partially correct
35 Partially correct 122 ms 37020 KB Partially correct
36 Partially correct 267 ms 38080 KB Partially correct
37 Partially correct 265 ms 38240 KB Partially correct
38 Partially correct 316 ms 38932 KB Partially correct
39 Partially correct 186 ms 39076 KB Partially correct
40 Partially correct 248 ms 38508 KB Partially correct
41 Partially correct 132 ms 38252 KB Partially correct
42 Partially correct 132 ms 38192 KB Partially correct
43 Partially correct 267 ms 38196 KB Partially correct
44 Partially correct 240 ms 37288 KB Partially correct
45 Partially correct 131 ms 38072 KB Partially correct
46 Partially correct 129 ms 38028 KB Partially correct
47 Partially correct 145 ms 38348 KB Partially correct
48 Partially correct 134 ms 37228 KB Partially correct
49 Partially correct 125 ms 38812 KB Partially correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 123 ms 34968 KB Partially correct
2 Incorrect 120 ms 34972 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 29712 KB Partially correct
2 Partially correct 286 ms 37732 KB Partially correct
3 Partially correct 276 ms 38044 KB Partially correct
4 Partially correct 148 ms 38504 KB Partially correct
5 Partially correct 152 ms 39068 KB Partially correct
6 Partially correct 259 ms 38936 KB Partially correct
7 Partially correct 132 ms 38772 KB Partially correct
8 Partially correct 128 ms 37732 KB Partially correct
9 Partially correct 259 ms 38160 KB Partially correct
10 Partially correct 266 ms 38700 KB Partially correct
11 Partially correct 222 ms 37908 KB Partially correct
12 Partially correct 140 ms 39072 KB Partially correct
13 Partially correct 312 ms 37996 KB Partially correct
14 Partially correct 129 ms 37480 KB Partially correct
15 Partially correct 133 ms 37924 KB Partially correct
16 Partially correct 253 ms 38408 KB Partially correct
17 Partially correct 255 ms 39580 KB Partially correct
18 Partially correct 190 ms 37324 KB Partially correct
19 Partially correct 137 ms 37752 KB Partially correct
20 Partially correct 200 ms 37460 KB Partially correct
21 Partially correct 127 ms 38700 KB Partially correct
22 Partially correct 128 ms 37732 KB Partially correct
23 Partially correct 269 ms 38044 KB Partially correct
24 Partially correct 291 ms 38288 KB Partially correct
25 Partially correct 147 ms 37744 KB Partially correct
26 Partially correct 128 ms 38256 KB Partially correct
27 Partially correct 130 ms 37540 KB Partially correct
28 Partially correct 133 ms 37592 KB Partially correct
29 Partially correct 127 ms 38240 KB Partially correct
30 Partially correct 268 ms 38356 KB Partially correct
31 Partially correct 264 ms 37552 KB Partially correct
32 Partially correct 135 ms 39028 KB Partially correct
33 Partially correct 277 ms 38048 KB Partially correct
34 Partially correct 258 ms 38568 KB Partially correct
35 Partially correct 134 ms 37400 KB Partially correct
36 Partially correct 122 ms 37020 KB Partially correct
37 Partially correct 267 ms 38080 KB Partially correct
38 Partially correct 265 ms 38240 KB Partially correct
39 Partially correct 316 ms 38932 KB Partially correct
40 Partially correct 186 ms 39076 KB Partially correct
41 Partially correct 248 ms 38508 KB Partially correct
42 Partially correct 132 ms 38252 KB Partially correct
43 Partially correct 132 ms 38192 KB Partially correct
44 Partially correct 267 ms 38196 KB Partially correct
45 Partially correct 240 ms 37288 KB Partially correct
46 Partially correct 131 ms 38072 KB Partially correct
47 Partially correct 129 ms 38028 KB Partially correct
48 Partially correct 145 ms 38348 KB Partially correct
49 Partially correct 134 ms 37228 KB Partially correct
50 Partially correct 125 ms 38812 KB Partially correct
51 Partially correct 123 ms 34968 KB Partially correct
52 Incorrect 120 ms 34972 KB Not correct
53 Halted 0 ms 0 KB -