oj.uz

Submission #1072182

# Submission time Handle Problem Language Result Execution time Memory
1072182 2024-08-23T15:16:30 Z edogawa_something The Ties That Guide Us (CEOI23_incursion) C++17
9 / 100
 278 ms 41296 KB 
#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll M=5e5+10;
const ll inf=2e18;
vii adj[M];
bool vis[M];
ll dis[M],pa[M],dep[M];
void mdfs(ll x,ll d=0) {
  if(vis[x])
    return;
  vis[x]=1;
  dis[x]=d;
  for(auto it:adj[x]) {
    if(it==pa[x])
      continue;
    pa[it]=x;
    mdfs(it,d+1);
    dep[x]=max(dep[x],dep[it]+1);
  }
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
  for(int i=0;i<F.size();i++)
    adj[F[i].F].pb(F[i].S),adj[F[i].S].pb(F[i].F);
  mdfs(safe);
  vector<int>res;
  for(int i=1;i<=F.size()+1;i++)
    res.pb(dis[i]);
  return res;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
  for(int i=1;i<F.size()+2;i++)
    adj[i].clear();
  for(int i=0;i<F.size();i++)
    adj[F[i].F].pb(F[i].S),adj[F[i].S].pb(F[i].F);
  ll n=F.size()+1;
  for(int i=0;i<n;i++)
    vis[i+1]=pa[i+1]=dis[i+1]=dep[i+1]=0;
  mdfs(curr);
  ll lt=t;
  for(int i=1;i<=n;i++)
    vis[i]=0;
  while(t!=0) {
    random_shuffle(all(adj[curr]));
    for(auto it:adj[curr]) {
      //cout<<curr<<' '<<it<<' '<<dep[it]<<' '<<t<<endl;
      if(it==pa[curr]||dep[it]<t-1)
        continue;
      ll tt=visit(int(it));
      if(tt>t)
        visit(curr);
      else {
        t=tt;
        curr=it;
        break;
      }
    }
  }
}
/*
10 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10


*/

Compilation message

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=0;i<F.size();i++)
      |               ~^~~~~~~~~
incursion.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=1;i<=F.size()+1;i++)
      |               ~^~~~~~~~~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int i=1;i<F.size()+2;i++)
      |               ~^~~~~~~~~~~
incursion.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<F.size();i++)
      |               ~^~~~~~~~~
incursion.cpp:46:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |     vis[i+1]=pa[i+1]=dis[i+1]=dep[i+1]=0;
      |              ~~~~~~~^~~~~~~~~~~~~~~~~~~~
incursion.cpp:48:6: warning: unused variable 'lt' [-Wunused-variable]
   48 |   ll lt=t;
      |      ^~
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 11 ms 27936 KB Partially correct

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 221 ms 39900 KB Partially correct
2 Partially correct 227 ms 39856 KB Partially correct
3 Partially correct 117 ms 41024 KB Partially correct
4 Partially correct 113 ms 39236 KB Partially correct
5 Partially correct 217 ms 39880 KB Partially correct
6 Partially correct 92 ms 37852 KB Partially correct
7 Partially correct 91 ms 37884 KB Partially correct
8 Partially correct 234 ms 39900 KB Partially correct
9 Partially correct 212 ms 39912 KB Partially correct
10 Partially correct 175 ms 39320 KB Partially correct
11 Partially correct 111 ms 40064 KB Partially correct
12 Partially correct 278 ms 40648 KB Partially correct
13 Partially correct 93 ms 38048 KB Partially correct
14 Partially correct 88 ms 37956 KB Partially correct
15 Partially correct 229 ms 39780 KB Partially correct
16 Partially correct 218 ms 39856 KB Partially correct
17 Partially correct 140 ms 39328 KB Partially correct
18 Partially correct 104 ms 40604 KB Partially correct
19 Partially correct 164 ms 40076 KB Partially correct
20 Partially correct 93 ms 38044 KB Partially correct
21 Partially correct 87 ms 37864 KB Partially correct
22 Partially correct 219 ms 39980 KB Partially correct
23 Partially correct 226 ms 39852 KB Partially correct
24 Partially correct 93 ms 39336 KB Partially correct
25 Partially correct 93 ms 41296 KB Partially correct
26 Partially correct 98 ms 39660 KB Partially correct
27 Partially correct 83 ms 38044 KB Partially correct
28 Partially correct 88 ms 38044 KB Partially correct
29 Partially correct 226 ms 39864 KB Partially correct
30 Partially correct 240 ms 39856 KB Partially correct
31 Partially correct 101 ms 38800 KB Partially correct
32 Partially correct 258 ms 40120 KB Partially correct
33 Partially correct 253 ms 40348 KB Partially correct
34 Partially correct 97 ms 37968 KB Partially correct
35 Partially correct 99 ms 37956 KB Partially correct
36 Partially correct 214 ms 39716 KB Partially correct
37 Partially correct 229 ms 39888 KB Partially correct
38 Partially correct 262 ms 40528 KB Partially correct
39 Partially correct 156 ms 40056 KB Partially correct
40 Partially correct 214 ms 39584 KB Partially correct
41 Partially correct 83 ms 38048 KB Partially correct
42 Partially correct 82 ms 38044 KB Partially correct
43 Partially correct 226 ms 39904 KB Partially correct
44 Partially correct 234 ms 39968 KB Partially correct
45 Partially correct 98 ms 39836 KB Partially correct
46 Partially correct 90 ms 40264 KB Partially correct
47 Partially correct 107 ms 39580 KB Partially correct
48 Partially correct 90 ms 38200 KB Partially correct
49 Partially correct 92 ms 38140 KB Partially correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 93 ms 35408 KB Partially correct
2 Partially correct 94 ms 35400 KB Partially correct
3 Partially correct 90 ms 35512 KB Partially correct
4 Partially correct 97 ms 38188 KB Partially correct
5 Partially correct 156 ms 38200 KB Partially correct
6 Partially correct 176 ms 38736 KB Partially correct
7 Incorrect 82 ms 35484 KB Not correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 27936 KB Partially correct
2 Partially correct 221 ms 39900 KB Partially correct
3 Partially correct 227 ms 39856 KB Partially correct
4 Partially correct 117 ms 41024 KB Partially correct
5 Partially correct 113 ms 39236 KB Partially correct
6 Partially correct 217 ms 39880 KB Partially correct
7 Partially correct 92 ms 37852 KB Partially correct
8 Partially correct 91 ms 37884 KB Partially correct
9 Partially correct 234 ms 39900 KB Partially correct
10 Partially correct 212 ms 39912 KB Partially correct
11 Partially correct 175 ms 39320 KB Partially correct
12 Partially correct 111 ms 40064 KB Partially correct
13 Partially correct 278 ms 40648 KB Partially correct
14 Partially correct 93 ms 38048 KB Partially correct
15 Partially correct 88 ms 37956 KB Partially correct
16 Partially correct 229 ms 39780 KB Partially correct
17 Partially correct 218 ms 39856 KB Partially correct
18 Partially correct 140 ms 39328 KB Partially correct
19 Partially correct 104 ms 40604 KB Partially correct
20 Partially correct 164 ms 40076 KB Partially correct
21 Partially correct 93 ms 38044 KB Partially correct
22 Partially correct 87 ms 37864 KB Partially correct
23 Partially correct 219 ms 39980 KB Partially correct
24 Partially correct 226 ms 39852 KB Partially correct
25 Partially correct 93 ms 39336 KB Partially correct
26 Partially correct 93 ms 41296 KB Partially correct
27 Partially correct 98 ms 39660 KB Partially correct
28 Partially correct 83 ms 38044 KB Partially correct
29 Partially correct 88 ms 38044 KB Partially correct
30 Partially correct 226 ms 39864 KB Partially correct
31 Partially correct 240 ms 39856 KB Partially correct
32 Partially correct 101 ms 38800 KB Partially correct
33 Partially correct 258 ms 40120 KB Partially correct
34 Partially correct 253 ms 40348 KB Partially correct
35 Partially correct 97 ms 37968 KB Partially correct
36 Partially correct 99 ms 37956 KB Partially correct
37 Partially correct 214 ms 39716 KB Partially correct
38 Partially correct 229 ms 39888 KB Partially correct
39 Partially correct 262 ms 40528 KB Partially correct
40 Partially correct 156 ms 40056 KB Partially correct
41 Partially correct 214 ms 39584 KB Partially correct
42 Partially correct 83 ms 38048 KB Partially correct
43 Partially correct 82 ms 38044 KB Partially correct
44 Partially correct 226 ms 39904 KB Partially correct
45 Partially correct 234 ms 39968 KB Partially correct
46 Partially correct 98 ms 39836 KB Partially correct
47 Partially correct 90 ms 40264 KB Partially correct
48 Partially correct 107 ms 39580 KB Partially correct
49 Partially correct 90 ms 38200 KB Partially correct
50 Partially correct 92 ms 38140 KB Partially correct
51 Partially correct 93 ms 35408 KB Partially correct
52 Partially correct 94 ms 35400 KB Partially correct
53 Partially correct 90 ms 35512 KB Partially correct
54 Partially correct 97 ms 38188 KB Partially correct
55 Partially correct 156 ms 38200 KB Partially correct
56 Partially correct 176 ms 38736 KB Partially correct
57 Incorrect 82 ms 35484 KB Not correct
58 Halted 0 ms 0 KB -