oj.uz

Submission #1072173

# Submission time Handle Problem Language Result Execution time Memory
1072173 2024-08-23T15:11:42 Z edogawa_something The Ties That Guide Us (CEOI23_incursion) C++17
9 / 100
 285 ms 41256 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) {
    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 219 ms 39852 KB Partially correct
2 Partially correct 223 ms 39860 KB Partially correct
3 Partially correct 121 ms 41256 KB Partially correct
4 Partially correct 139 ms 39472 KB Partially correct
5 Partially correct 217 ms 39580 KB Partially correct
6 Partially correct 92 ms 37952 KB Partially correct
7 Partially correct 99 ms 37872 KB Partially correct
8 Partially correct 232 ms 39900 KB Partially correct
9 Partially correct 259 ms 39880 KB Partially correct
10 Partially correct 166 ms 39144 KB Partially correct
11 Partially correct 107 ms 39928 KB Partially correct
12 Partially correct 285 ms 40540 KB Partially correct
13 Partially correct 90 ms 38044 KB Partially correct
14 Partially correct 81 ms 37960 KB Partially correct
15 Partially correct 216 ms 39856 KB Partially correct
16 Partially correct 229 ms 39856 KB Partially correct
17 Partially correct 147 ms 39492 KB Partially correct
18 Partially correct 99 ms 40804 KB Partially correct
19 Partially correct 168 ms 40068 KB Partially correct
20 Partially correct 86 ms 37940 KB Partially correct
21 Partially correct 88 ms 37944 KB Partially correct
22 Partially correct 216 ms 39988 KB Partially correct
23 Partially correct 221 ms 39860 KB Partially correct
24 Partially correct 101 ms 39324 KB Partially correct
25 Partially correct 81 ms 41120 KB Partially correct
26 Partially correct 99 ms 39996 KB Partially correct
27 Partially correct 87 ms 37864 KB Partially correct
28 Partially correct 87 ms 38052 KB Partially correct
29 Partially correct 206 ms 39892 KB Partially correct
30 Partially correct 196 ms 39860 KB Partially correct
31 Partially correct 107 ms 38700 KB Partially correct
32 Partially correct 238 ms 40268 KB Partially correct
33 Partially correct 252 ms 40300 KB Partially correct
34 Partially correct 86 ms 37944 KB Partially correct
35 Partially correct 99 ms 38008 KB Partially correct
36 Partially correct 240 ms 39880 KB Partially correct
37 Partially correct 251 ms 39880 KB Partially correct
38 Partially correct 274 ms 40616 KB Partially correct
39 Partially correct 139 ms 40348 KB Partially correct
40 Partially correct 177 ms 39656 KB Partially correct
41 Partially correct 95 ms 37940 KB Partially correct
42 Partially correct 88 ms 38044 KB Partially correct
43 Partially correct 214 ms 39984 KB Partially correct
44 Partially correct 225 ms 39872 KB Partially correct
45 Partially correct 111 ms 40000 KB Partially correct
46 Partially correct 92 ms 40244 KB Partially correct
47 Partially correct 102 ms 39584 KB Partially correct
48 Partially correct 91 ms 38044 KB Partially correct
49 Partially correct 86 ms 37936 KB Partially correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 81 ms 35396 KB Partially correct
2 Partially correct 82 ms 35648 KB Partially correct
3 Partially correct 87 ms 35580 KB Partially correct
4 Partially correct 99 ms 38044 KB Partially correct
5 Partially correct 145 ms 38204 KB Partially correct
6 Partially correct 187 ms 38556 KB Partially correct
7 Incorrect 87 ms 35628 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 219 ms 39852 KB Partially correct
3 Partially correct 223 ms 39860 KB Partially correct
4 Partially correct 121 ms 41256 KB Partially correct
5 Partially correct 139 ms 39472 KB Partially correct
6 Partially correct 217 ms 39580 KB Partially correct
7 Partially correct 92 ms 37952 KB Partially correct
8 Partially correct 99 ms 37872 KB Partially correct
9 Partially correct 232 ms 39900 KB Partially correct
10 Partially correct 259 ms 39880 KB Partially correct
11 Partially correct 166 ms 39144 KB Partially correct
12 Partially correct 107 ms 39928 KB Partially correct
13 Partially correct 285 ms 40540 KB Partially correct
14 Partially correct 90 ms 38044 KB Partially correct
15 Partially correct 81 ms 37960 KB Partially correct
16 Partially correct 216 ms 39856 KB Partially correct
17 Partially correct 229 ms 39856 KB Partially correct
18 Partially correct 147 ms 39492 KB Partially correct
19 Partially correct 99 ms 40804 KB Partially correct
20 Partially correct 168 ms 40068 KB Partially correct
21 Partially correct 86 ms 37940 KB Partially correct
22 Partially correct 88 ms 37944 KB Partially correct
23 Partially correct 216 ms 39988 KB Partially correct
24 Partially correct 221 ms 39860 KB Partially correct
25 Partially correct 101 ms 39324 KB Partially correct
26 Partially correct 81 ms 41120 KB Partially correct
27 Partially correct 99 ms 39996 KB Partially correct
28 Partially correct 87 ms 37864 KB Partially correct
29 Partially correct 87 ms 38052 KB Partially correct
30 Partially correct 206 ms 39892 KB Partially correct
31 Partially correct 196 ms 39860 KB Partially correct
32 Partially correct 107 ms 38700 KB Partially correct
33 Partially correct 238 ms 40268 KB Partially correct
34 Partially correct 252 ms 40300 KB Partially correct
35 Partially correct 86 ms 37944 KB Partially correct
36 Partially correct 99 ms 38008 KB Partially correct
37 Partially correct 240 ms 39880 KB Partially correct
38 Partially correct 251 ms 39880 KB Partially correct
39 Partially correct 274 ms 40616 KB Partially correct
40 Partially correct 139 ms 40348 KB Partially correct
41 Partially correct 177 ms 39656 KB Partially correct
42 Partially correct 95 ms 37940 KB Partially correct
43 Partially correct 88 ms 38044 KB Partially correct
44 Partially correct 214 ms 39984 KB Partially correct
45 Partially correct 225 ms 39872 KB Partially correct
46 Partially correct 111 ms 40000 KB Partially correct
47 Partially correct 92 ms 40244 KB Partially correct
48 Partially correct 102 ms 39584 KB Partially correct
49 Partially correct 91 ms 38044 KB Partially correct
50 Partially correct 86 ms 37936 KB Partially correct
51 Partially correct 81 ms 35396 KB Partially correct
52 Partially correct 82 ms 35648 KB Partially correct
53 Partially correct 87 ms 35580 KB Partially correct
54 Partially correct 99 ms 38044 KB Partially correct
55 Partially correct 145 ms 38204 KB Partially correct
56 Partially correct 187 ms 38556 KB Partially correct
57 Incorrect 87 ms 35628 KB Not correct
58 Halted 0 ms 0 KB -