oj.uz

Submission #730461

# Submission time Handle Problem Language Result Execution time Memory
730461 2023-04-26T00:41:03 Z n0sk1ll Amusement Park (JOI17_amusement_park) C++17
28 / 100
 23 ms 3616 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#include "Joi.h"

namespace joi
{
    int up[10004];

    int Up(int x)
    {
        if (up[x]<0) return x;
        return up[x]=Up(up[x]);
    }

    void build(int n)
    {
        ff(i,0,n) up[i]=-1;
    }

    bool dsu(int a, int b)
    {
        a=Up(a),b=Up(b);
        if (a==b) return false;
        if (up[a]<up[b]) swap(a,b);
        up[b]+=up[a],up[a]=b;
        return true;
    }

    bool broj[60];
    graph g(10004);
    int tb=0;

    void dfs(int p, int q)
    {
        MessageBoard(p,broj[tb++]);
        if (tb==60) tb=0;

        for (auto it : g[p]) if (it!=q) dfs(it,p);
    }

    void solve(int n, int m, int A[], int B[], li x)
    {
        build(n);
        ff(i,0,m) if (dsu(A[i],B[i])) g[A[i]].pb(B[i]),g[B[i]].pb(A[i]);

        ff(i,0,60) broj[i]=((x>>i)&1);

        dfs(0,-1);
    }
}

using namespace joi;

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
    solve(N,M,A,B,X);
}

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#include "Ioi.h"

namespace ioi
{
    int up[10004];

    int Up(int x)
    {
        if (up[x]<0) return x;
        return up[x]=Up(up[x]);
    }

    void build(int n)
    {
        ff(i,0,n) up[i]=-1;
    }

    bool dsu(int a, int b)
    {
        a=Up(a),b=Up(b);
        if (a==b) return false;
        if (up[a]<up[b]) swap(a,b);
        up[b]+=up[a],up[a]=b;
        return true;
    }

    bool broj[60];
    graph g(10004);
    int boja[10004];
    int tb=0;

    void dfs(int p, int q)
    {
        boja[p]=tb++;
        if (tb==60) tb=0;

        for (auto it : g[p]) if (it!=q) dfs(it,p);
    }

    bool uklj[69];
    int kolko=0;
    li ans=0;

    void klizaj(int p, int q)
    {
        if (kolko==60) return;
        int sta=Move(p);
        if (!uklj[boja[p]])
        {
            uklj[boja[p]]=1,kolko++;
            if (sta) ans|=(1ll<<boja[p]);
        }
        if (kolko==60) return;

        for (auto it : g[p]) if (it!=q) klizaj(it,p);
        if (kolko==60) return;

        Move(q);
    }

    li solve(int n, int m, int A[], int B[], int P, int V)
    {
        build(n);
        ff(i,0,m) if (dsu(A[i],B[i])) g[A[i]].pb(B[i]),g[B[i]].pb(A[i]);

        dfs(0,-1);

        uklj[boja[P]]=1,kolko++;
        if (V) ans|=(1ll<<boja[P]);

        for (auto it : g[P]) klizaj(it,P);
        return ans;
    }
}

using namespace ioi;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    return solve(N,M,A,B,P,V);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1036 KB Output is correct
2 Correct 2 ms 1040 KB Output is correct
3 Correct 2 ms 1156 KB Output is correct
4 Correct 2 ms 1128 KB Output is correct
5 Correct 2 ms 1048 KB Output is correct
6 Correct 2 ms 1144 KB Output is correct
7 Correct 2 ms 1272 KB Output is correct
8 Correct 2 ms 1180 KB Output is correct
9 Correct 1 ms 1044 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 4 ms 1380 KB Output is correct
12 Correct 2 ms 1040 KB Output is correct
13 Correct 2 ms 1164 KB Output is correct
14 Correct 2 ms 1172 KB Output is correct
15 Correct 2 ms 1128 KB Output is correct
16 Correct 2 ms 1260 KB Output is correct
17 Correct 2 ms 1056 KB Output is correct
18 Correct 2 ms 1296 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3172 KB Output is correct
2 Correct 19 ms 3584 KB Output is correct
3 Correct 19 ms 3556 KB Output is correct
4 Correct 15 ms 2868 KB Output is correct
5 Correct 15 ms 3340 KB Output is correct
6 Correct 13 ms 3104 KB Output is correct
7 Correct 13 ms 3136 KB Output is correct
8 Correct 13 ms 3120 KB Output is correct
9 Correct 13 ms 3144 KB Output is correct
10 Correct 12 ms 2872 KB Output is correct
11 Correct 11 ms 2912 KB Output is correct
12 Correct 13 ms 2724 KB Output is correct
13 Correct 17 ms 2700 KB Output is correct
14 Correct 12 ms 2828 KB Output is correct
15 Correct 12 ms 2804 KB Output is correct
16 Correct 13 ms 2892 KB Output is correct
17 Correct 13 ms 2840 KB Output is correct
18 Correct 12 ms 2872 KB Output is correct
19 Correct 13 ms 2868 KB Output is correct
20 Correct 12 ms 3296 KB Output is correct
21 Correct 12 ms 3376 KB Output is correct
22 Correct 16 ms 3088 KB Output is correct
23 Correct 13 ms 3128 KB Output is correct
24 Correct 13 ms 3124 KB Output is correct
25 Correct 16 ms 3200 KB Output is correct
26 Correct 13 ms 3196 KB Output is correct
27 Correct 14 ms 3100 KB Output is correct
28 Correct 13 ms 3104 KB Output is correct
29 Correct 14 ms 2968 KB Output is correct
30 Correct 14 ms 3096 KB Output is correct
31 Correct 2 ms 1044 KB Output is correct
32 Correct 1 ms 1176 KB Output is correct
33 Correct 2 ms 1180 KB Output is correct
34 Correct 2 ms 1040 KB Output is correct
35 Correct 1 ms 1036 KB Output is correct
36 Correct 2 ms 1128 KB Output is correct
37 Correct 2 ms 1188 KB Output is correct
38 Correct 2 ms 1048 KB Output is correct
39 Correct 2 ms 1140 KB Output is correct
40 Correct 2 ms 1044 KB Output is correct
41 Correct 1 ms 1048 KB Output is correct
42 Correct 2 ms 1048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1044 KB Output is correct
2 Correct 1 ms 1040 KB Output is correct
3 Correct 1 ms 1044 KB Output is correct
4 Correct 3 ms 1604 KB Output is correct
5 Correct 2 ms 1592 KB Output is correct
6 Correct 2 ms 1592 KB Output is correct
7 Correct 2 ms 1600 KB Output is correct
8 Correct 3 ms 1592 KB Output is correct
9 Correct 11 ms 3616 KB Output is correct
10 Correct 11 ms 3612 KB Output is correct
11 Correct 11 ms 3616 KB Output is correct
12 Correct 2 ms 1140 KB Output is correct
13 Correct 1 ms 1048 KB Output is correct
14 Correct 2 ms 1040 KB Output is correct
15 Correct 1 ms 1040 KB Output is correct

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Partially correct 20 ms 3192 KB Partially correct
2 Correct 19 ms 3588 KB Output is correct
3 Partially correct 20 ms 3616 KB Partially correct
4 Correct 15 ms 2884 KB Output is correct
5 Partially correct 13 ms 3468 KB Partially correct
6 Partially correct 13 ms 3116 KB Partially correct
7 Partially correct 13 ms 3192 KB Partially correct
8 Partially correct 12 ms 3096 KB Partially correct
9 Partially correct 13 ms 3124 KB Partially correct
10 Correct 15 ms 2832 KB Output is correct
11 Correct 15 ms 2852 KB Output is correct
12 Correct 12 ms 2700 KB Output is correct
13 Partially correct 11 ms 2712 KB Partially correct
14 Partially correct 12 ms 2820 KB Partially correct
15 Correct 13 ms 2756 KB Output is correct
16 Correct 14 ms 2832 KB Output is correct
17 Correct 12 ms 2848 KB Output is correct
18 Partially correct 14 ms 2936 KB Partially correct
19 Partially correct 18 ms 2816 KB Partially correct
20 Incorrect 11 ms 3384 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3168 KB Output is correct
2 Incorrect 23 ms 3592 KB Output isn't correct
3 Halted 0 ms 0 KB -