oj.uz

Submission #361504

# Submission time Handle Problem Language Result Execution time Memory
361504 2021-01-30T10:12:32 Z Thistle Amusement Park (JOI17_amusement_park) C++14
100 / 100
 867 ms 65228 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define vec vector
#define vi vec<ll>
#define pb emplace_back
#define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),0,(n))
#define siz(a) int((a).size())
#define all(a) (a).begin(), (a).end()


void Joi(int N, int M, int A[], int B[], long long X, int T) {
  int n=N;
  vec<vi>e(n,vi()),f(n,vi()),h(n,vi());
  rep(i,M){
    f[A[i]].pb(B[i]);
    f[B[i]].pb(A[i]);
  }
  vec<bool>used(n,0);
  auto dfs=[&](int x,auto& dfs)->void{
    used[x]=1;
    for(auto g:f[x]){
      if(!used[g]){
        e[x].pb(g);h[x].pb(g);h[g].pb(x);
        dfs(g,dfs);
      }
    }
  };
  dfs(0,dfs);
  queue<int>se;rep(i,60) se.push(i);
  set<int>se2;
  vec<set<int>>po(n,set<int>());
  vi num(n,0),tr(n,-1);
  auto dfs2=[&](int x,auto& dfs2)->void{
    if(!se.empty()) {
      num[x]=se.front();se.pop();
      tr[x]=0;
      se2.insert(x);
    }
    for(auto g:e[x]) dfs2(g,dfs2);
  };
  dfs2(0,dfs2);
  rep(i,n) if(!tr[i]) po[i]=se2;
  auto dfs3=[&](int x,auto& dfs3)->void{
    if(tr[x]<0){
      for(auto g:h[x]) if(~tr[g]){
        int leaf=-1;
        for(auto r:po[g]){
          if(r==g) continue;
          int sum=0;
          for(auto k:h[r]){
            if(po[g].find(k)!=po[g].end()) sum++;
          }
          if(sum==1){
            leaf=r;
          }
        }
        po[x].insert(x);
        for(auto r:po[g]){
          if(r!=leaf) po[x].insert(r);
          else num[x]=num[r];
        }
        tr[x]=0;
        break;
      }
    }
    for(auto g:e[x]) dfs3(g,dfs3);
  };dfs3(0,dfs3);
  rep(i,n) MessageBoard(i,(X>>num[i])&1);
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define vec vector
#define vi vec<ll>
#define pb emplace_back
#define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),0,(n))
#define siz(a) int((a).size())
#define all(a) (a).begin(), (a).end()


long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  int n=N;
  vec<vi>e(n,vi()),f(n,vi()),h(n,vi());
  rep(i,M){
    f[A[i]].pb(B[i]);
    f[B[i]].pb(A[i]);
  }
  vec<bool>used(n,0);
  auto dfs=[&](int x,auto& dfs)->void{
    used[x]=1;
    for(auto g:f[x]){
      if(!used[g]){
        e[x].pb(g);h[x].pb(g);h[g].pb(x);
        dfs(g,dfs);
      }
    }
  };
  dfs(0,dfs);
  queue<int>se;rep(i,60) se.push(i);
  set<int>se2;
  vec<set<int>>po(n,set<int>());
  vi num(n,0),tr(n,-1);
  auto dfs2=[&](int x,auto& dfs2)->void{
    if(!se.empty()) {
      num[x]=se.front();se.pop();
      tr[x]=0;
      se2.insert(x);
    }
    for(auto g:e[x]) dfs2(g,dfs2);
  };
  dfs2(0,dfs2);
  rep(i,n) if(!tr[i]) po[i]=se2;
  auto dfs3=[&](int x,auto& dfs3)->void{
    if(tr[x]<0){
      for(auto g:h[x]) if(~tr[g]){
        int leaf=-1;
        for(auto r:po[g]){
          if(r==g) continue;
          int sum=0;
          for(auto k:h[r]){
            if(po[g].find(k)!=po[g].end()) sum++;
          }
          if(sum==1){
            leaf=r;
          }
        }
        po[x].insert(x);
        for(auto r:po[g]){
          if(r!=leaf) po[x].insert(r);
          else num[x]=num[r];
        }
        tr[x]=0;
        break;
      }
    }
    for(auto g:e[x]) dfs3(g,dfs3);
  };dfs3(0,dfs3);

  ll ans=ll(V)<<num[P];
  auto dfs5=[&](int x,int p,auto& dfs5)->void{
    for(auto g:h[x]){
      if(g==p||po[P].find(g)==po[P].end())continue;
      ll t=Move(g);
      ans|=(t<<num[g]);
      dfs5(g,x,dfs5);
    }
    if(~p) Move(p);
  };dfs5(P,-1,dfs5);
  return ans;
}

Compilation message

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:17:3: note: in expansion of macro 'rep'
   17 |   rep(i,M){
      |   ^~~
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:32:16: note: in expansion of macro 'rep'
   32 |   queue<int>se;rep(i,60) se.push(i);
      |                ^~~
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(i,n) if(!tr[i]) po[i]=se2;
      |   ^~~
Joi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Joi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Joi.cpp:71:3: note: in expansion of macro 'rep'
   71 |   rep(i,n) MessageBoard(i,(X>>num[i])&1);
      |   ^~~

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Ioi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Ioi.cpp:17:3: note: in expansion of macro 'rep'
   17 |   rep(i,M){
      |   ^~~
Ioi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Ioi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Ioi.cpp:32:16: note: in expansion of macro 'rep'
   32 |   queue<int>se;rep(i,60) se.push(i);
      |                ^~~
Ioi.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rng(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
      |                           ^
Ioi.cpp:9:18: note: in expansion of macro 'rng'
    9 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
Ioi.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(i,n) if(!tr[i]) po[i]=se2;
      |   ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1252 KB Output is correct
2 Correct 4 ms 1636 KB Output is correct
3 Correct 8 ms 2544 KB Output is correct
4 Correct 4 ms 1384 KB Output is correct
5 Correct 3 ms 1384 KB Output is correct
6 Correct 4 ms 1768 KB Output is correct
7 Correct 9 ms 2740 KB Output is correct
8 Correct 6 ms 2544 KB Output is correct
9 Correct 8 ms 2288 KB Output is correct
10 Correct 4 ms 1640 KB Output is correct
11 Correct 7 ms 2184 KB Output is correct
12 Correct 2 ms 1000 KB Output is correct
13 Correct 8 ms 2672 KB Output is correct
14 Correct 8 ms 2736 KB Output is correct
15 Correct 8 ms 2544 KB Output is correct
16 Correct 8 ms 2544 KB Output is correct
17 Correct 8 ms 2700 KB Output is correct
18 Correct 10 ms 2544 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 64840 KB Output is correct
2 Correct 391 ms 64900 KB Output is correct
3 Correct 372 ms 65228 KB Output is correct
4 Correct 362 ms 62600 KB Output is correct
5 Correct 349 ms 64156 KB Output is correct
6 Correct 384 ms 63568 KB Output is correct
7 Correct 388 ms 63252 KB Output is correct
8 Correct 381 ms 63532 KB Output is correct
9 Correct 367 ms 63740 KB Output is correct
10 Correct 867 ms 63024 KB Output is correct
11 Correct 836 ms 62800 KB Output is correct
12 Correct 305 ms 56844 KB Output is correct
13 Correct 301 ms 56944 KB Output is correct
14 Correct 319 ms 59792 KB Output is correct
15 Correct 827 ms 62792 KB Output is correct
16 Correct 834 ms 62520 KB Output is correct
17 Correct 373 ms 62612 KB Output is correct
18 Correct 378 ms 62884 KB Output is correct
19 Correct 376 ms 62604 KB Output is correct
20 Correct 255 ms 63880 KB Output is correct
21 Correct 248 ms 62748 KB Output is correct
22 Correct 385 ms 63220 KB Output is correct
23 Correct 383 ms 63388 KB Output is correct
24 Correct 384 ms 63132 KB Output is correct
25 Correct 386 ms 63476 KB Output is correct
26 Correct 387 ms 63560 KB Output is correct
27 Correct 391 ms 63568 KB Output is correct
28 Correct 384 ms 63612 KB Output is correct
29 Correct 353 ms 57796 KB Output is correct
30 Correct 370 ms 60304 KB Output is correct
31 Correct 4 ms 1640 KB Output is correct
32 Correct 5 ms 1768 KB Output is correct
33 Correct 6 ms 2544 KB Output is correct
34 Correct 4 ms 1680 KB Output is correct
35 Correct 2 ms 1384 KB Output is correct
36 Correct 2 ms 1256 KB Output is correct
37 Correct 2 ms 1128 KB Output is correct
38 Correct 2 ms 1164 KB Output is correct
39 Correct 2 ms 1000 KB Output is correct
40 Correct 2 ms 1384 KB Output is correct
41 Correct 4 ms 1384 KB Output is correct
42 Correct 2 ms 1128 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1448 KB Output is correct
2 Correct 2 ms 1252 KB Output is correct
3 Correct 2 ms 1432 KB Output is correct
4 Correct 37 ms 11216 KB Output is correct
5 Correct 37 ms 11300 KB Output is correct
6 Correct 37 ms 11208 KB Output is correct
7 Correct 39 ms 11172 KB Output is correct
8 Correct 39 ms 11208 KB Output is correct
9 Correct 235 ms 64368 KB Output is correct
10 Correct 238 ms 64196 KB Output is correct
11 Correct 236 ms 64156 KB Output is correct
12 Correct 2 ms 1172 KB Output is correct
13 Correct 2 ms 1256 KB Output is correct
14 Correct 2 ms 1140 KB Output is correct
15 Correct 2 ms 1128 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 64760 KB Output is correct
2 Correct 377 ms 65096 KB Output is correct
3 Correct 379 ms 65096 KB Output is correct
4 Correct 352 ms 62616 KB Output is correct
5 Correct 351 ms 64408 KB Output is correct
6 Correct 377 ms 63516 KB Output is correct
7 Correct 385 ms 63516 KB Output is correct
8 Correct 379 ms 63176 KB Output is correct
9 Correct 380 ms 63196 KB Output is correct
10 Correct 834 ms 62468 KB Output is correct
11 Correct 855 ms 62528 KB Output is correct
12 Correct 312 ms 57228 KB Output is correct
13 Correct 303 ms 56836 KB Output is correct
14 Correct 326 ms 59780 KB Output is correct
15 Correct 812 ms 63160 KB Output is correct
16 Correct 836 ms 62660 KB Output is correct
17 Correct 386 ms 62732 KB Output is correct
18 Correct 386 ms 62492 KB Output is correct
19 Correct 385 ms 62732 KB Output is correct
20 Correct 252 ms 63776 KB Output is correct
21 Correct 250 ms 62840 KB Output is correct
22 Correct 389 ms 63388 KB Output is correct
23 Correct 392 ms 63344 KB Output is correct
24 Correct 389 ms 63376 KB Output is correct
25 Correct 383 ms 63516 KB Output is correct
26 Correct 386 ms 63548 KB Output is correct
27 Correct 390 ms 63692 KB Output is correct
28 Correct 387 ms 63292 KB Output is correct
29 Correct 350 ms 57604 KB Output is correct
30 Correct 362 ms 60364 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 64884 KB Output is correct
2 Correct 377 ms 65224 KB Output is correct
3 Correct 374 ms 65108 KB Output is correct
4 Correct 355 ms 62608 KB Output is correct
5 Correct 351 ms 64648 KB Output is correct
6 Correct 388 ms 63132 KB Output is correct
7 Correct 375 ms 63192 KB Output is correct
8 Correct 382 ms 63492 KB Output is correct
9 Correct 379 ms 63472 KB Output is correct
10 Correct 863 ms 62664 KB Output is correct
11 Correct 833 ms 62368 KB Output is correct
12 Correct 300 ms 57072 KB Output is correct
13 Correct 309 ms 56844 KB Output is correct
14 Correct 315 ms 59672 KB Output is correct
15 Correct 786 ms 62844 KB Output is correct
16 Correct 822 ms 62528 KB Output is correct
17 Correct 376 ms 62756 KB Output is correct
18 Correct 383 ms 62732 KB Output is correct
19 Correct 387 ms 62788 KB Output is correct
20 Correct 256 ms 64144 KB Output is correct
21 Correct 252 ms 62748 KB Output is correct
22 Correct 392 ms 63400 KB Output is correct
23 Correct 383 ms 63500 KB Output is correct
24 Correct 387 ms 63628 KB Output is correct
25 Correct 390 ms 63724 KB Output is correct
26 Correct 386 ms 63344 KB Output is correct
27 Correct 387 ms 63940 KB Output is correct
28 Correct 390 ms 63900 KB Output is correct
29 Correct 349 ms 58064 KB Output is correct
30 Correct 367 ms 60684 KB Output is correct
31 Correct 5 ms 1668 KB Output is correct
32 Correct 4 ms 1768 KB Output is correct
33 Correct 7 ms 2672 KB Output is correct
34 Correct 4 ms 1680 KB Output is correct
35 Correct 3 ms 1384 KB Output is correct
36 Correct 2 ms 1256 KB Output is correct
37 Correct 2 ms 1128 KB Output is correct
38 Correct 2 ms 1172 KB Output is correct
39 Correct 2 ms 1128 KB Output is correct
40 Correct 3 ms 1452 KB Output is correct
41 Correct 4 ms 1408 KB Output is correct
42 Correct 2 ms 1264 KB Output is correct