oj.uz

Submission #1064816

# Submission time Handle Problem Language Result Execution time Memory
1064816 2024-08-18T18:10:04 Z beaconmc The Ties That Guide Us (CEOI23_incursion) C++17
12 / 100
 312 ms 40056 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 (idk.size()==3 && idk[0][0]==idk[2][0]) unsure[curr] = 2;





        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]] && unsure[curr]){
                if (visited[idk[idk.size()-2][1]] && !unsure[idk[idk.size()-2][1]] && unsure[curr]==2)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 3 ms 30204 KB Partially correct

Subtask #1
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 242 ms 38340 KB Partially correct
2 Partially correct 237 ms 38556 KB Partially correct
3 Partially correct 137 ms 39324 KB Partially correct
4 Partially correct 133 ms 39652 KB Partially correct
5 Partially correct 240 ms 39500 KB Partially correct
6 Partially correct 97 ms 39584 KB Partially correct
7 Partially correct 117 ms 38396 KB Partially correct
8 Partially correct 243 ms 38688 KB Partially correct
9 Partially correct 250 ms 39072 KB Partially correct
10 Partially correct 190 ms 38408 KB Partially correct
11 Partially correct 118 ms 39580 KB Partially correct
12 Partially correct 312 ms 38504 KB Partially correct
13 Partially correct 111 ms 38044 KB Partially correct
14 Partially correct 104 ms 38244 KB Partially correct
15 Partially correct 236 ms 39268 KB Partially correct
16 Partially correct 260 ms 40056 KB Partially correct
17 Partially correct 169 ms 37916 KB Partially correct
18 Partially correct 128 ms 38392 KB Partially correct
19 Partially correct 182 ms 37908 KB Partially correct
20 Partially correct 105 ms 39536 KB Partially correct
21 Partially correct 110 ms 38504 KB Partially correct
22 Partially correct 252 ms 38752 KB Partially correct
23 Partially correct 243 ms 38724 KB Partially correct
24 Partially correct 128 ms 38556 KB Partially correct
25 Partially correct 100 ms 38968 KB Partially correct
26 Partially correct 116 ms 38228 KB Partially correct
27 Partially correct 111 ms 38248 KB Partially correct
28 Partially correct 106 ms 38812 KB Partially correct
29 Partially correct 227 ms 38788 KB Partially correct
30 Partially correct 245 ms 37980 KB Partially correct
31 Partially correct 113 ms 39700 KB Partially correct
32 Partially correct 250 ms 38928 KB Partially correct
33 Partially correct 297 ms 39088 KB Partially correct
34 Partially correct 110 ms 38052 KB Partially correct
35 Partially correct 109 ms 37788 KB Partially correct
36 Partially correct 241 ms 39328 KB Partially correct
37 Partially correct 239 ms 38764 KB Partially correct
38 Partially correct 291 ms 39548 KB Partially correct
39 Partially correct 172 ms 39596 KB Partially correct
40 Partially correct 217 ms 39328 KB Partially correct
41 Partially correct 105 ms 39020 KB Partially correct
42 Partially correct 113 ms 39072 KB Partially correct
43 Partially correct 228 ms 38972 KB Partially correct
44 Partially correct 243 ms 37752 KB Partially correct
45 Partially correct 115 ms 38300 KB Partially correct
46 Partially correct 112 ms 38300 KB Partially correct
47 Partially correct 119 ms 39132 KB Partially correct
48 Partially correct 107 ms 37964 KB Partially correct
49 Partially correct 109 ms 39276 KB Partially correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 104 ms 35480 KB Partially correct
2 Incorrect 109 ms 35484 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 30204 KB Partially correct
2 Partially correct 242 ms 38340 KB Partially correct
3 Partially correct 237 ms 38556 KB Partially correct
4 Partially correct 137 ms 39324 KB Partially correct
5 Partially correct 133 ms 39652 KB Partially correct
6 Partially correct 240 ms 39500 KB Partially correct
7 Partially correct 97 ms 39584 KB Partially correct
8 Partially correct 117 ms 38396 KB Partially correct
9 Partially correct 243 ms 38688 KB Partially correct
10 Partially correct 250 ms 39072 KB Partially correct
11 Partially correct 190 ms 38408 KB Partially correct
12 Partially correct 118 ms 39580 KB Partially correct
13 Partially correct 312 ms 38504 KB Partially correct
14 Partially correct 111 ms 38044 KB Partially correct
15 Partially correct 104 ms 38244 KB Partially correct
16 Partially correct 236 ms 39268 KB Partially correct
17 Partially correct 260 ms 40056 KB Partially correct
18 Partially correct 169 ms 37916 KB Partially correct
19 Partially correct 128 ms 38392 KB Partially correct
20 Partially correct 182 ms 37908 KB Partially correct
21 Partially correct 105 ms 39536 KB Partially correct
22 Partially correct 110 ms 38504 KB Partially correct
23 Partially correct 252 ms 38752 KB Partially correct
24 Partially correct 243 ms 38724 KB Partially correct
25 Partially correct 128 ms 38556 KB Partially correct
26 Partially correct 100 ms 38968 KB Partially correct
27 Partially correct 116 ms 38228 KB Partially correct
28 Partially correct 111 ms 38248 KB Partially correct
29 Partially correct 106 ms 38812 KB Partially correct
30 Partially correct 227 ms 38788 KB Partially correct
31 Partially correct 245 ms 37980 KB Partially correct
32 Partially correct 113 ms 39700 KB Partially correct
33 Partially correct 250 ms 38928 KB Partially correct
34 Partially correct 297 ms 39088 KB Partially correct
35 Partially correct 110 ms 38052 KB Partially correct
36 Partially correct 109 ms 37788 KB Partially correct
37 Partially correct 241 ms 39328 KB Partially correct
38 Partially correct 239 ms 38764 KB Partially correct
39 Partially correct 291 ms 39548 KB Partially correct
40 Partially correct 172 ms 39596 KB Partially correct
41 Partially correct 217 ms 39328 KB Partially correct
42 Partially correct 105 ms 39020 KB Partially correct
43 Partially correct 113 ms 39072 KB Partially correct
44 Partially correct 228 ms 38972 KB Partially correct
45 Partially correct 243 ms 37752 KB Partially correct
46 Partially correct 115 ms 38300 KB Partially correct
47 Partially correct 112 ms 38300 KB Partially correct
48 Partially correct 119 ms 39132 KB Partially correct
49 Partially correct 107 ms 37964 KB Partially correct
50 Partially correct 109 ms 39276 KB Partially correct
51 Partially correct 104 ms 35480 KB Partially correct
52 Incorrect 109 ms 35484 KB Not correct
53 Halted 0 ms 0 KB -