oj.uz

Submission #1048540

# Submission time Handle Problem Language Result Execution time Memory
1048540 2024-08-08T08:12:40 Z ibm2006 The Ties That Guide Us (CEOI23_incursion) C++17
60 / 100
 227 ms 77972 KB 
#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],par[1100000],c[1100000],h[1100000],siz[1100000],realcurr,realt,safe;
vector<ll> v[1100000],u;
pair<ll,pair<ll,ll>> p;
void Clear()
{
    ll i;
    u.clear();
    for(i=1;i<=n;i++)
    {
        v[i].clear();
        siz[i]=0;
        par[i]=0;
        h[i]=0;
        c[i]=0;
    }
}
void get_siz(ll x,ll y)
{
    ll i;
    siz[x]=1;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        get_siz(v[x][i],x);
        siz[x]+=siz[v[x][i]];
    }
}
ll centroid(ll x,ll y,ll z)
{
    ll i;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        if(siz[v[x][i]]*2>n)
            return centroid(v[x][i],x,z);
    }
    return x;
}
ll dfs(ll x,ll y)
{
    if(x==t)
    {
        u[x-1]=1;
        return 1;
    }
    if(x==0)
        return 0;
    ll i;
    c[x]=1;
    for(i=0;i<h[x];i++)
    {
        if(c[v[x][i]])
            continue;
        if(dfs(v[x][i],x))
        {
            u[x-1]=1;
            return 1;
        }
    }
    return 0;
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
n=F.size()+1;
Clear();
t=safe;
for(i=0;i<n-1;i++)
{
    x=F[i].first;
    y=F[i].second;
    v[x].push_back(y);
    v[y].push_back(x);
    h[x]++;
    h[y]++;
}
get_siz(1,0);
x=centroid(1,0,siz[1]);
get_siz(x,0);
y=0;
for(i=0;i<v[x].size();i++)
{
    y=v[x][i];
    if((n-siz[y])*2<=n)
    {
        break;
    }
    y=0;
}
c[x]=1;
c[y]=1;
u.resize(n);
dfs(x,0);
dfs(y,0);
return u;
}
ll ask(ll x)
{
    if(x==0)
        return 0;
    if(realcurr==x)
    {
        return realt;
    }
    realcurr=x;
    realt=visit(x);
    return realt;
}
void f(ll x,ll y)
{
    par[x]=y;
    ll i;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y||c[v[x][i]])
            continue;
        f(v[x][i],x);
    }
}
pair<ll,pair<ll,ll>> get_child(ll x)
{
    ll i;
    pair<ll,pair<ll,ll>> p={0,{0,0}};
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==par[x]||c[v[x][i]])
            continue;
        if(p.first==0)
            p.first=v[x][i];
        else if(p.second.first==0)
            p.second.first=v[x][i];
            else
                p.second.second=v[x][i];
    }
    return p;
}
ll subtree(ll x,ll y,ll z)
{
    if(x==z)
        return 1;
    ll i;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y||c[v[x][i]])
            continue;
        if(subtree(v[x][i],x,z))
            return 1;
    }
    return 0;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
n=F.size()+1;
Clear();
realcurr=curr;
realt=t;
for(i=0;i<n-1;i++)
{
    x=F[i].first;
    y=F[i].second;
    v[x].push_back(y);
    v[y].push_back(x);
    h[x]++;
    h[y]++;
}
get_siz(1,0);
x=centroid(1,0,siz[1]);
get_siz(x,0);
y=0;
for(i=0;i<v[x].size();i++)
{
    y=v[x][i];
    if((n-siz[y])*2<=n)
    {
        break;
    }
    y=0;
}
c[x]=1;
c[y]=1;
f(x,0);
f(y,0);
if(subtree(y,0,curr))
{
    swap(x,y);
}
while(!t)
{
    if(curr==x)
    {
        break;
    }
    curr=par[curr];
    t=visit(curr);
}
if(t==0)
    {curr=y;
    swap(x,y);
    t=visit(x);
    }
get_siz(x,0);
while(1)
{
    p=get_child(curr);
    if(siz[p.first]<siz[p.second.first])
        swap(p.first,p.second.first);
    if(siz[p.first]<siz[p.second.second])
        swap(p.first,p.second.second);
    if(siz[p.second.first]<siz[p.second.second])
        swap(p.second.first,p.second.second);
    t=ask(p.first);
    if(t==1)
    {
        curr=p.first;
        continue;
    }
    t=ask(curr);
    t=ask(p.second.first);
    if(t==1)
    {
        curr=p.second.first;
        continue;
    }
    t=ask(curr);
    t=ask(p.second.second);
    if(t==1)
    {
        curr=p.second.second;
        continue;
    }
    t=ask(curr);
    break;
}
return;
}

Compilation message

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:85:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 | for(i=0;i<v[x].size();i++)
      |         ~^~~~~~~~~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:173:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 | for(i=0;i<v[x].size();i++)
      |         ~^~~~~~~~~~~~
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 Incorrect 8 ms 66820 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 75748 KB Correct
2 Correct 209 ms 76084 KB Correct
3 Correct 107 ms 76956 KB Correct
4 Correct 100 ms 77468 KB Correct
5 Correct 175 ms 77204 KB Correct
6 Correct 84 ms 77376 KB Correct
7 Correct 89 ms 75900 KB Correct
8 Correct 180 ms 76120 KB Correct
9 Correct 217 ms 76968 KB Correct
10 Correct 159 ms 76100 KB Correct
11 Correct 106 ms 77540 KB Correct
12 Correct 227 ms 76144 KB Correct
13 Correct 86 ms 75580 KB Correct
14 Correct 84 ms 76196 KB Correct
15 Correct 201 ms 76732 KB Correct
16 Correct 193 ms 77972 KB Correct
17 Correct 126 ms 75088 KB Correct
18 Correct 89 ms 75844 KB Correct
19 Correct 141 ms 75268 KB Correct
20 Correct 90 ms 77124 KB Correct
21 Correct 90 ms 76336 KB Correct
22 Correct 175 ms 76252 KB Correct
23 Correct 198 ms 76440 KB Correct
24 Correct 100 ms 75688 KB Correct
25 Correct 88 ms 76784 KB Correct
26 Correct 91 ms 75592 KB Correct
27 Correct 81 ms 75992 KB Correct
28 Correct 79 ms 76336 KB Correct
29 Correct 202 ms 76504 KB Correct
30 Correct 186 ms 75508 KB Correct
31 Correct 93 ms 77516 KB Correct
32 Correct 217 ms 76468 KB Correct
33 Correct 203 ms 76500 KB Correct
34 Correct 87 ms 75592 KB Correct
35 Correct 88 ms 75320 KB Correct
36 Correct 171 ms 76372 KB Correct
37 Correct 193 ms 76572 KB Correct
38 Correct 209 ms 77156 KB Correct
39 Correct 152 ms 77620 KB Correct
40 Correct 186 ms 77020 KB Correct
41 Correct 86 ms 76700 KB Correct
42 Correct 91 ms 76444 KB Correct
43 Correct 186 ms 76620 KB Correct
44 Correct 185 ms 75196 KB Correct
45 Correct 86 ms 75840 KB Correct
46 Correct 90 ms 75840 KB Correct
47 Correct 103 ms 76700 KB Correct
48 Correct 83 ms 75456 KB Correct
49 Correct 84 ms 76960 KB Correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 71388 KB Correct
2 Correct 83 ms 71336 KB Correct
3 Correct 73 ms 71392 KB Correct
4 Correct 91 ms 74696 KB Correct
5 Correct 121 ms 73884 KB Correct
6 Correct 151 ms 73884 KB Correct
7 Correct 76 ms 71080 KB Correct
8 Correct 76 ms 71212 KB Correct
9 Correct 74 ms 71228 KB Correct
10 Correct 74 ms 71068 KB Correct
11 Correct 78 ms 71152 KB Correct
12 Correct 76 ms 71236 KB Correct
13 Correct 74 ms 71036 KB Correct
14 Correct 57 ms 70128 KB Correct
15 Correct 52 ms 70120 KB Correct
16 Correct 88 ms 71324 KB Correct
17 Correct 72 ms 71212 KB Correct
18 Correct 71 ms 71236 KB Correct
19 Correct 73 ms 71324 KB Correct
20 Correct 53 ms 70124 KB Correct
21 Correct 55 ms 70108 KB Correct
22 Correct 53 ms 70064 KB Correct
23 Correct 55 ms 70128 KB Correct
24 Correct 60 ms 70228 KB Correct
25 Correct 58 ms 70108 KB Correct
26 Correct 77 ms 71236 KB Correct
27 Correct 77 ms 71068 KB Correct
28 Correct 81 ms 71136 KB Correct
29 Correct 83 ms 71396 KB Correct
30 Correct 86 ms 71328 KB Correct
31 Correct 82 ms 71392 KB Correct
32 Correct 80 ms 71512 KB Correct
33 Correct 75 ms 71076 KB Correct
34 Correct 75 ms 71488 KB Correct
35 Correct 74 ms 71224 KB Correct
36 Correct 70 ms 71492 KB Correct
37 Correct 78 ms 71332 KB Correct
38 Correct 73 ms 71072 KB Correct
39 Correct 78 ms 71324 KB Correct
40 Correct 82 ms 71368 KB Correct
41 Correct 77 ms 71232 KB Correct
42 Correct 78 ms 71336 KB Correct
43 Correct 76 ms 71452 KB Correct
44 Correct 74 ms 71324 KB Correct
45 Correct 73 ms 70976 KB Correct
46 Correct 79 ms 71488 KB Correct
47 Correct 75 ms 71492 KB Correct
48 Correct 75 ms 71408 KB Correct
49 Correct 83 ms 71064 KB Correct
50 Correct 73 ms 71232 KB Correct
51 Correct 78 ms 71216 KB Correct
52 Correct 84 ms 71484 KB Correct
53 Correct 73 ms 71068 KB Correct
54 Correct 81 ms 71500 KB Correct
55 Correct 86 ms 71112 KB Correct
56 Correct 78 ms 71580 KB Correct
57 Correct 73 ms 71628 KB Correct
58 Correct 74 ms 71580 KB Correct
59 Correct 83 ms 71584 KB Correct
60 Correct 75 ms 71472 KB Correct
61 Correct 75 ms 71368 KB Correct
62 Correct 75 ms 72092 KB Correct
63 Correct 78 ms 71744 KB Correct
64 Correct 76 ms 71388 KB Correct
65 Correct 78 ms 71464 KB Correct

Subtask #3
0.0 / 40.0

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