oj.uz

Submission #959814

# Submission time Handle Problem Language Result Execution time Memory
959814 2024-04-09T07:15:27 Z andrei_boaca Stray Cat (JOI20_stray) C++17
100 / 100
 57 ms 19936 KB 
#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
namespace
{
    pii a={0,0},b={0,1},c={1,1};
    vector<pii> vec={b,c,b,b,b,a};
    map<pii,int> myind;
    int INF=1e9;
    vector<int> muchii[20005];
    vector<pii> g;
    int dist[20005];
    int par[20005];
    int n,m;
    void bfs()
    {
        for(int i=0;i<n;i++)
            dist[i]=INF;
        dist[0]=0;
        queue<int> coada;
        coada.push(0);
        while(!coada.empty())
        {
            int nod=coada.front();
            coada.pop();
            for(int i:muchii[nod])
                if(dist[i]>dist[nod]+1)
                {
                    dist[i]=dist[nod]+1;
                    coada.push(i);
                }
        }
    }
    int garbage(int x)
    {
        if(x%3==0)
            return 0;
        if(x%3==1)
            return 1;
        return 2;
    }
    vector<int> subtask14()
    {
        vector<int> sol;
        for(int i=0;i<m;i++)
        {
            int a=g[i].first,b=g[i].second;
            if(dist[a]>dist[b])
                swap(a,b);
            int val=garbage(dist[a]);
            sol.push_back(val);
        }
        return sol;
    }
    vector<int> sol;
    void dfs(int nod)
    {
        if(nod==0)
        {
            for(int i:muchii[nod])
                if(i!=par[nod])
                {
                    par[i]=nod;
                    int ind=myind[{nod,i}];
                    sol[ind]=0;
                    dfs(i);
                }
            return;
        }
        if(muchii[nod].size()>=3)
        {
            int c=sol[myind[{nod,par[nod]}]];
            c=1-c;
            for(int i:muchii[nod])
                if(i!=par[nod])
                {
                    par[i]=nod;
                    int ind=myind[{nod,i}];
                    sol[ind]=c;
                    dfs(i);
                }
            return;
        }
        int cul=sol[myind[{nod,par[nod]}]];
        int poz;
        if(cul==0)
            poz=5;
        else
            poz=1;
        while(true)
        {
            if(muchii[nod].size()>2)
            {
                dfs(nod);
                break;
            }
            if(muchii[nod].size()==1)
                break;
            int nxt=(muchii[nod][0]^muchii[nod][1]^par[nod]);
            int c=sol[myind[{nod,par[nod]}]];
            c=(vec[poz].first^vec[poz].second^c);
            sol[myind[{nod,nxt}]]=c;
            par[nxt]=nod;
            poz++;
            poz%=6;
            nod=nxt;
        }
    }
}
/// a={0,0}, b={0,1}, c={1,1}
vector<int> Mark(int N, int M, int A, int B,vector<int> U, vector<int> V)
{
    n=N;
    m=M;
    for(int i=0;i<m;i++)
    {
        int a=U[i],b=V[i];
        muchii[a].push_back(b);
        muchii[b].push_back(a);
        g.push_back({a,b});
        myind[{a,b}]=myind[{b,a}]=i;
    }
    bfs();
    if(B==0)
    {
        vector<int> sol=subtask14();
        return sol;
    }
    par[0]=-1;
    sol.resize(m);
    dfs(0);
    return sol;
}

#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
namespace
{
    bool penal;
    int sure, prv;
    pii aa={0,0},bb={0,1},cc={1,1};
    vector<vector<pii>> bad={{aa,bb,cc},{cc,bb,bb},{bb,bb,bb,aa},{bb,bb,aa,bb},{bb,aa,bb,cc},{bb,cc,bb,bb}};
    vector<pii> v;
    pii gettype(vector<int> y)
    {
        if(y[0]==2)
            return aa;
        if(y[1]==2)
            return cc;
        return bb;
    }
}

void Init(int A, int B)
{
    if(B==0)
        penal=1;
    prv=-1;
    sure=0;
}
int Move(vector<int> y)
{
    if(penal)
    {
        int cnt=0;
        for(int i=0;i<3;i++)
            if(y[i]!=0)
                cnt++;
        if(cnt==1)
        {
            for(int i=0;i<3;i++)
                if(y[i]>0)
                    return i;
        }
        if(y[0]>0&&y[1]>0)
            return 0;
        if(y[0]>0&&y[2]>0)
            return 2;
        return 1;
    }
    if(prv==-1)
    {
        if(y[0]+y[1]!=2)
        {
            sure=1;
            if(y[0]==1)
            {
                prv=0;
                return 0;
            }
            else
            {
                prv=1;
                return 1;
            }
        }
        pii x=gettype(y);
        v.push_back(x);
        prv=x.first;
        return x.first;
    }
    if(sure==0)
    {
        if(y[0]+y[1]>=2)
        {
            sure=1;
            y[prv]++;
            if(y[prv]==1)
                return -1;
            else
            {
                prv=1-prv;
                return prv;
            }
        }
        if(y[0]+y[1]==0)
        {
            sure=1;
            return -1;
        }
        y[prv]++;
        pii x=gettype(y);
        v.push_back(x);
        for(auto j:bad)
        {
            if(j==v)
            {
                sure=1;
                return -1;
            }
        }
        y[prv]--;
        if(v.size()>=4)
            sure=1;
        if(y[0]>=1)
        {
            prv=0;
            return 0;
        }
        if(y[1]>=1)
        {
            prv=1;
            return 1;
        }
    }
    if(sure==1)
    {
        if(y[0]>=1&&y[1]>=1)
        {
            int cul=1-prv;
            prv=cul;
            return cul;
        }
        if(y[0]>=1)
        {
            prv=0;
            return 0;
        }
        if(y[1]>=1)
        {
            prv=1;
            return 1;
        }
    }

}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:136:1: warning: control reaches end of non-void function [-Wreturn-type]
  136 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 18800 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 42 ms 18268 KB Output is correct
4 Correct 50 ms 19692 KB Output is correct
5 Correct 49 ms 19936 KB Output is correct
6 Correct 47 ms 18648 KB Output is correct
7 Correct 49 ms 18572 KB Output is correct
8 Correct 44 ms 19388 KB Output is correct
9 Correct 44 ms 19280 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 18800 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 42 ms 18268 KB Output is correct
4 Correct 50 ms 19692 KB Output is correct
5 Correct 49 ms 19936 KB Output is correct
6 Correct 47 ms 18648 KB Output is correct
7 Correct 49 ms 18572 KB Output is correct
8 Correct 44 ms 19388 KB Output is correct
9 Correct 44 ms 19280 KB Output is correct
10 Correct 48 ms 16296 KB Output is correct
11 Correct 39 ms 16568 KB Output is correct
12 Correct 44 ms 16676 KB Output is correct
13 Correct 39 ms 16308 KB Output is correct
14 Correct 40 ms 16820 KB Output is correct
15 Correct 43 ms 17236 KB Output is correct
16 Correct 41 ms 19500 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16208 KB Output is correct
2 Correct 2 ms 1296 KB Output is correct
3 Correct 40 ms 15796 KB Output is correct
4 Correct 56 ms 17520 KB Output is correct
5 Correct 50 ms 17596 KB Output is correct
6 Correct 52 ms 16216 KB Output is correct
7 Correct 39 ms 16096 KB Output is correct
8 Correct 45 ms 17096 KB Output is correct
9 Correct 46 ms 17012 KB Output is correct
10 Correct 41 ms 16864 KB Output is correct
11 Correct 44 ms 16788 KB Output is correct
12 Correct 45 ms 16728 KB Output is correct
13 Correct 45 ms 16692 KB Output is correct
14 Correct 43 ms 16968 KB Output is correct
15 Correct 48 ms 17136 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16208 KB Output is correct
2 Correct 2 ms 1296 KB Output is correct
3 Correct 40 ms 15796 KB Output is correct
4 Correct 56 ms 17520 KB Output is correct
5 Correct 50 ms 17596 KB Output is correct
6 Correct 52 ms 16216 KB Output is correct
7 Correct 39 ms 16096 KB Output is correct
8 Correct 45 ms 17096 KB Output is correct
9 Correct 46 ms 17012 KB Output is correct
10 Correct 41 ms 16864 KB Output is correct
11 Correct 44 ms 16788 KB Output is correct
12 Correct 45 ms 16728 KB Output is correct
13 Correct 45 ms 16692 KB Output is correct
14 Correct 43 ms 16968 KB Output is correct
15 Correct 48 ms 17136 KB Output is correct
16 Correct 40 ms 14744 KB Output is correct
17 Correct 35 ms 14940 KB Output is correct
18 Correct 35 ms 14536 KB Output is correct
19 Correct 35 ms 14540 KB Output is correct
20 Correct 39 ms 15308 KB Output is correct
21 Correct 37 ms 15196 KB Output is correct
22 Correct 40 ms 17360 KB Output is correct
23 Correct 41 ms 14692 KB Output is correct
24 Correct 45 ms 14720 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1564 KB Output is correct
2 Correct 1 ms 1300 KB Output is correct
3 Correct 2 ms 1568 KB Output is correct
4 Correct 3 ms 1564 KB Output is correct
5 Correct 3 ms 1564 KB Output is correct
6 Correct 2 ms 1564 KB Output is correct
7 Correct 2 ms 1564 KB Output is correct
8 Correct 2 ms 1568 KB Output is correct
9 Correct 2 ms 2624 KB Output is correct
10 Correct 2 ms 1564 KB Output is correct
11 Correct 2 ms 1564 KB Output is correct
12 Correct 2 ms 1564 KB Output is correct
13 Correct 3 ms 1560 KB Output is correct
14 Correct 1 ms 1576 KB Output is correct
15 Correct 2 ms 1568 KB Output is correct
16 Correct 2 ms 1572 KB Output is correct
17 Correct 2 ms 1556 KB Output is correct
18 Correct 3 ms 1564 KB Output is correct
19 Correct 2 ms 1564 KB Output is correct
20 Correct 3 ms 1556 KB Output is correct
21 Correct 3 ms 1568 KB Output is correct
22 Correct 2 ms 1572 KB Output is correct
23 Correct 2 ms 1572 KB Output is correct
24 Correct 2 ms 1564 KB Output is correct
25 Correct 2 ms 1616 KB Output is correct
26 Correct 3 ms 1616 KB Output is correct
27 Correct 2 ms 1564 KB Output is correct
28 Correct 2 ms 1448 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14236 KB Output is correct
2 Correct 43 ms 15256 KB Output is correct
3 Correct 1 ms 1308 KB Output is correct
4 Correct 38 ms 14240 KB Output is correct
5 Correct 57 ms 15728 KB Output is correct
6 Correct 51 ms 15736 KB Output is correct
7 Correct 43 ms 14880 KB Output is correct
8 Correct 41 ms 14636 KB Output is correct
9 Correct 45 ms 15928 KB Output is correct
10 Correct 45 ms 15672 KB Output is correct
11 Correct 45 ms 16044 KB Output is correct
12 Correct 44 ms 15704 KB Output is correct
13 Correct 45 ms 15884 KB Output is correct
14 Correct 45 ms 15544 KB Output is correct
15 Correct 56 ms 15828 KB Output is correct
16 Correct 46 ms 15680 KB Output is correct
17 Correct 44 ms 15612 KB Output is correct
18 Correct 46 ms 15556 KB Output is correct
19 Correct 41 ms 15472 KB Output is correct
20 Correct 48 ms 15456 KB Output is correct
21 Correct 47 ms 15560 KB Output is correct
22 Correct 46 ms 15444 KB Output is correct
23 Correct 40 ms 14208 KB Output is correct
24 Correct 44 ms 14292 KB Output is correct
25 Correct 48 ms 14544 KB Output is correct
26 Correct 41 ms 14444 KB Output is correct
27 Correct 44 ms 15564 KB Output is correct
28 Correct 43 ms 15376 KB Output is correct
29 Correct 49 ms 15468 KB Output is correct
30 Correct 43 ms 15476 KB Output is correct
31 Correct 40 ms 14220 KB Output is correct
32 Correct 48 ms 14188 KB Output is correct
33 Correct 41 ms 14584 KB Output is correct
34 Correct 39 ms 14524 KB Output is correct
35 Correct 48 ms 15296 KB Output is correct
36 Correct 43 ms 15104 KB Output is correct
37 Correct 49 ms 15264 KB Output is correct
38 Correct 43 ms 15324 KB Output is correct
39 Correct 45 ms 15256 KB Output is correct
40 Correct 44 ms 15228 KB Output is correct
41 Correct 44 ms 15552 KB Output is correct
42 Correct 44 ms 15560 KB Output is correct
43 Correct 44 ms 15500 KB Output is correct
44 Correct 49 ms 15716 KB Output is correct
45 Correct 45 ms 15484 KB Output is correct
46 Correct 46 ms 15412 KB Output is correct
47 Correct 42 ms 15096 KB Output is correct
48 Correct 42 ms 15000 KB Output is correct
49 Correct 42 ms 14960 KB Output is correct
50 Correct 48 ms 15064 KB Output is correct
51 Correct 41 ms 14284 KB Output is correct
52 Correct 39 ms 14376 KB Output is correct
53 Correct 41 ms 14268 KB Output is correct
54 Correct 40 ms 14452 KB Output is correct
55 Correct 41 ms 14288 KB Output is correct
56 Correct 44 ms 14524 KB Output is correct
57 Correct 43 ms 14544 KB Output is correct
58 Correct 42 ms 14460 KB Output is correct
59 Correct 41 ms 14604 KB Output is correct
60 Correct 46 ms 14848 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 14192 KB Output is correct
2 Correct 43 ms 15144 KB Output is correct
3 Correct 1 ms 1296 KB Output is correct
4 Correct 37 ms 14224 KB Output is correct
5 Correct 53 ms 15732 KB Output is correct
6 Correct 44 ms 15756 KB Output is correct
7 Correct 41 ms 14732 KB Output is correct
8 Correct 40 ms 14808 KB Output is correct
9 Correct 45 ms 15864 KB Output is correct
10 Correct 46 ms 15808 KB Output is correct
11 Correct 48 ms 15732 KB Output is correct
12 Correct 46 ms 15816 KB Output is correct
13 Correct 44 ms 15740 KB Output is correct
14 Correct 46 ms 15748 KB Output is correct
15 Correct 46 ms 15732 KB Output is correct
16 Correct 44 ms 15688 KB Output is correct
17 Correct 56 ms 15476 KB Output is correct
18 Correct 49 ms 15796 KB Output is correct
19 Correct 43 ms 15608 KB Output is correct
20 Correct 44 ms 15560 KB Output is correct
21 Correct 43 ms 15548 KB Output is correct
22 Correct 48 ms 15556 KB Output is correct
23 Correct 40 ms 14264 KB Output is correct
24 Correct 40 ms 14412 KB Output is correct
25 Correct 47 ms 14448 KB Output is correct
26 Correct 41 ms 14536 KB Output is correct
27 Correct 44 ms 15560 KB Output is correct
28 Correct 46 ms 15568 KB Output is correct
29 Correct 45 ms 15384 KB Output is correct
30 Correct 44 ms 15540 KB Output is correct
31 Correct 41 ms 14204 KB Output is correct
32 Correct 41 ms 14276 KB Output is correct
33 Correct 43 ms 14472 KB Output is correct
34 Correct 48 ms 14576 KB Output is correct
35 Correct 50 ms 15540 KB Output is correct
36 Correct 44 ms 15312 KB Output is correct
37 Correct 45 ms 15216 KB Output is correct
38 Correct 44 ms 15332 KB Output is correct
39 Correct 45 ms 15140 KB Output is correct
40 Correct 43 ms 15316 KB Output is correct
41 Correct 49 ms 15600 KB Output is correct
42 Correct 45 ms 15432 KB Output is correct
43 Correct 44 ms 15576 KB Output is correct
44 Correct 48 ms 15556 KB Output is correct
45 Correct 49 ms 15476 KB Output is correct
46 Correct 47 ms 15668 KB Output is correct
47 Correct 43 ms 14976 KB Output is correct
48 Correct 43 ms 14968 KB Output is correct
49 Correct 46 ms 15212 KB Output is correct
50 Correct 42 ms 15048 KB Output is correct
51 Correct 45 ms 14288 KB Output is correct
52 Correct 40 ms 14444 KB Output is correct
53 Correct 44 ms 14104 KB Output is correct
54 Correct 40 ms 14308 KB Output is correct
55 Correct 46 ms 14532 KB Output is correct
56 Correct 40 ms 14220 KB Output is correct
57 Correct 40 ms 14608 KB Output is correct
58 Correct 40 ms 14552 KB Output is correct
59 Correct 39 ms 14816 KB Output is correct
60 Correct 43 ms 14804 KB Output is correct