# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
212260 |
2020-03-22T16:01:10 Z |
zscoder |
Stray Cat (JOI20_stray) |
C++17 |
|
133 ms |
21324 KB |
#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
vector<ii> vec;
vector<ii> back;
struct Graph
{
struct edge
{
int v; ll weight;
};
vector<vector<edge> > adj;
int n;
Graph(int _n)
{
adj.resize(_n);
n = _n;
}
void addedge(int u, int v, ll c)
{
edge tmp;
tmp.v = v; tmp.weight = c;
adj[u].pb(tmp);
tmp.v = u;
adj[v].pb(tmp);
}
void reset()
{
adj.clear();
}
vector<ll> dist;
vi par;
void bfs(int s)
{
ll INFI = ll(1e18);
dist.assign(n, INFI);
par.assign(n, -1);
dist[s] = 0; par[s] = -1;
queue<int> q; q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i].v;
if(dist[v] >= INFI)
{
vec.pb({u,v});
dist[v] = dist[u] + 1;
par[v] = u;
q.push(v);
}
else
{
back.pb({u,v});
}
}
}
}
};
vi chain = {1,0,0,1,1,0};
int col[22222];
vi adj[22222];
int par[22222];
void dfs(int u, int p, int chainno=-1)
{
int child=0;
for(int v:adj[u])
{
if(v==p) continue;
par[v]=u;
child++;
}
if(child>=2)
{
for(int v:adj[u])
{
if(v==p) continue;
col[v]=col[u]^1;
dfs(v,u,-1);
}
}
else if(child==1)
{
for(int v:adj[u])
{
if(v==p) continue;
if(chainno>=0)
{
col[v] = chain[(chainno+1)%6];
dfs(v,u,(chainno+1)%6);
}
else
{
col[v]=col[u]^1;
if(col[v]==1) dfs(v,u,0);
else dfs(v,u,1);
}
}
}
}
std::vector<int> Mark(int N, int M, int A, int B,
std::vector<int> U, std::vector<int> V)
{
std::vector<int> ans(M);
int n=N; int m=M;
Graph G(n);
map<ii,int> ma;
for(int i=0;i<m;i++)
{
G.addedge(U[i],V[i],1);
ma[{U[i],V[i]}]=ma[{V[i],U[i]}]=i;
adj[U[i]].pb(V[i]);
adj[V[i]].pb(U[i]);
}
G.bfs(0);
if(A>=3)
{
for(ii x:vec)
{
int ed = ma[x];
int mind = min(G.dist[x.fi],G.dist[x.se]);
ans[ed]=mind%3;
}
for(ii x:back)
{
int ed = ma[x];
int mind = min(G.dist[x.fi],G.dist[x.se]);
ans[ed]=mind%3;
}
return ans;
}
col[0]=0;
dfs(0,-1);
for(int i=1;i<n;i++)
{
ans[ma[{i,par[i]}]] = col[i];
}
return ans;
}
#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
namespace {
int A, B;
int beg = 0;
int up=0;
vi path;
vi chain = {1,0,0,1,1,0};
} // namespace
void Init(int A, int B) {
::A = A;
::B = B;
::beg = 0;
::up = 0;
::path.clear();
}
int Move(std::vector<int> y)
{
if(A>=3)
{
int S[3]={};
int mx=0;
for(int i=0;i<3;i++)
{
if(y[i]>0)
{
mx=i; S[i]=1;
}
}
if(S[0]+S[1]+S[2]==1) return mx;
if(S[0]&&S[1]) return 0;
if(S[1]&&S[2]) return 1;
return 2;
}
else
{
//rmb to check leaf case
//cerr<<y[0]<<' '<<y[1]<<'\n';
if(up) //if we are certain we are going up
{
if(y[0]+y[1]==1)
{
if(y[0]==1){path.pb(0); return 0;}
path.pb(1); return 1;
}
path.pb((path.back()^1));
return path.back();
}
if(!beg)
{
if(y[0]+y[1]==1)
{
up=1;
if(y[1]==1){path.pb(1); return 1;}
else{path.pb(0); return 0;}
}
if(y[0]+y[1]>2)
{
up=1;
if(y[0]==1){path.pb(0); return 0;}
if(y[1]==1){path.pb(1); return 1;}
assert(0);
}
if(y[0]>0)
{
y[0]--; path.pb(0);
}
else
{
y[1]--; path.pb(1);
}
if(y[0]>0) path.pb(0);
else path.pb(1);
reverse(path.begin(),path.end());
beg=1;
return path.back();
}
//got previous liao
if(y[0]+y[1]==0)
{
up=1;
return -1; //can go back
}
if(y[0]==0&&y[1]>1)
{
up=1;
path.pb(0);
return -1;
}
if(y[0]>1&&y[1]==0)
{
up=1;
path.pb(1);
return -1;
}
if(y[0]+y[1]>1)
{
up=1;
y[path.back()]++;
if(y[0]==1)
{
path.pb(0);
return 0;
}
if(y[1]==1)
{
path.pb(1);
return 1;
}
assert(0);
}
//chain now
//cerr<<y[0]<<' '<<y[1]<<' '<<path[0]<<' '<<path.back()<<' '<<path.size()<<' '<<up<<'\n';
if(path.size()>=4)
{
vi V;
for(int i=int(path.size())-4;i<int(path.size());i++)
{
V.pb(path[i]);
}
if(y[0]==1)
{
V.pb(0);
}
else
{
V.pb(1);
}
bool pos=0;
for(int i=0;i<6;i++)
{
vi v2;
for(int j=i;j<i+5;j++)
{
v2.pb(chain[j%6]);
}
if(v2==V){pos=1; break;}
}
if(pos)
{
up=1; return -1;
}
else up=1;
}
if(y[0]==1)
{
path.pb(0); return 0;
}
if(y[1]==1)
{
path.pb(1); return 1;
}
assert(0);
}
}
Compilation message
Anthony.cpp: In member function 'void Graph::bfs(int)':
Anthony.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++)
~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
19932 KB |
Output is correct |
2 |
Correct |
10 ms |
1792 KB |
Output is correct |
3 |
Correct |
89 ms |
19388 KB |
Output is correct |
4 |
Correct |
130 ms |
21172 KB |
Output is correct |
5 |
Correct |
118 ms |
21324 KB |
Output is correct |
6 |
Correct |
101 ms |
19768 KB |
Output is correct |
7 |
Correct |
107 ms |
19756 KB |
Output is correct |
8 |
Correct |
108 ms |
20572 KB |
Output is correct |
9 |
Correct |
105 ms |
20548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
19932 KB |
Output is correct |
2 |
Correct |
10 ms |
1792 KB |
Output is correct |
3 |
Correct |
89 ms |
19388 KB |
Output is correct |
4 |
Correct |
130 ms |
21172 KB |
Output is correct |
5 |
Correct |
118 ms |
21324 KB |
Output is correct |
6 |
Correct |
101 ms |
19768 KB |
Output is correct |
7 |
Correct |
107 ms |
19756 KB |
Output is correct |
8 |
Correct |
108 ms |
20572 KB |
Output is correct |
9 |
Correct |
105 ms |
20548 KB |
Output is correct |
10 |
Correct |
98 ms |
17844 KB |
Output is correct |
11 |
Correct |
97 ms |
17768 KB |
Output is correct |
12 |
Correct |
101 ms |
17608 KB |
Output is correct |
13 |
Correct |
99 ms |
17716 KB |
Output is correct |
14 |
Correct |
101 ms |
18044 KB |
Output is correct |
15 |
Correct |
100 ms |
18400 KB |
Output is correct |
16 |
Correct |
106 ms |
20804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
17516 KB |
Output is correct |
2 |
Correct |
9 ms |
1792 KB |
Output is correct |
3 |
Correct |
87 ms |
17132 KB |
Output is correct |
4 |
Correct |
116 ms |
19116 KB |
Output is correct |
5 |
Correct |
113 ms |
18924 KB |
Output is correct |
6 |
Correct |
98 ms |
17500 KB |
Output is correct |
7 |
Correct |
86 ms |
17608 KB |
Output is correct |
8 |
Correct |
104 ms |
18236 KB |
Output is correct |
9 |
Correct |
95 ms |
18208 KB |
Output is correct |
10 |
Correct |
104 ms |
18008 KB |
Output is correct |
11 |
Correct |
103 ms |
18004 KB |
Output is correct |
12 |
Correct |
107 ms |
18124 KB |
Output is correct |
13 |
Correct |
107 ms |
18012 KB |
Output is correct |
14 |
Correct |
101 ms |
18436 KB |
Output is correct |
15 |
Correct |
114 ms |
18288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
17516 KB |
Output is correct |
2 |
Correct |
9 ms |
1792 KB |
Output is correct |
3 |
Correct |
87 ms |
17132 KB |
Output is correct |
4 |
Correct |
116 ms |
19116 KB |
Output is correct |
5 |
Correct |
113 ms |
18924 KB |
Output is correct |
6 |
Correct |
98 ms |
17500 KB |
Output is correct |
7 |
Correct |
86 ms |
17608 KB |
Output is correct |
8 |
Correct |
104 ms |
18236 KB |
Output is correct |
9 |
Correct |
95 ms |
18208 KB |
Output is correct |
10 |
Correct |
104 ms |
18008 KB |
Output is correct |
11 |
Correct |
103 ms |
18004 KB |
Output is correct |
12 |
Correct |
107 ms |
18124 KB |
Output is correct |
13 |
Correct |
107 ms |
18012 KB |
Output is correct |
14 |
Correct |
101 ms |
18436 KB |
Output is correct |
15 |
Correct |
114 ms |
18288 KB |
Output is correct |
16 |
Correct |
114 ms |
15868 KB |
Output is correct |
17 |
Correct |
104 ms |
15876 KB |
Output is correct |
18 |
Correct |
91 ms |
15728 KB |
Output is correct |
19 |
Correct |
133 ms |
16044 KB |
Output is correct |
20 |
Correct |
117 ms |
16568 KB |
Output is correct |
21 |
Correct |
106 ms |
16200 KB |
Output is correct |
22 |
Correct |
128 ms |
18532 KB |
Output is correct |
23 |
Correct |
84 ms |
15864 KB |
Output is correct |
24 |
Correct |
104 ms |
15956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2048 KB |
Output is correct |
2 |
Correct |
10 ms |
1792 KB |
Output is correct |
3 |
Correct |
11 ms |
2048 KB |
Output is correct |
4 |
Correct |
11 ms |
2048 KB |
Output is correct |
5 |
Correct |
11 ms |
2048 KB |
Output is correct |
6 |
Correct |
11 ms |
2048 KB |
Output is correct |
7 |
Correct |
11 ms |
2048 KB |
Output is correct |
8 |
Correct |
10 ms |
2048 KB |
Output is correct |
9 |
Correct |
11 ms |
2048 KB |
Output is correct |
10 |
Correct |
10 ms |
2048 KB |
Output is correct |
11 |
Correct |
11 ms |
2048 KB |
Output is correct |
12 |
Correct |
12 ms |
2048 KB |
Output is correct |
13 |
Correct |
13 ms |
2048 KB |
Output is correct |
14 |
Correct |
12 ms |
2048 KB |
Output is correct |
15 |
Correct |
13 ms |
2048 KB |
Output is correct |
16 |
Correct |
12 ms |
2048 KB |
Output is correct |
17 |
Correct |
11 ms |
2048 KB |
Output is correct |
18 |
Correct |
13 ms |
2048 KB |
Output is correct |
19 |
Correct |
12 ms |
2048 KB |
Output is correct |
20 |
Correct |
11 ms |
2000 KB |
Output is correct |
21 |
Correct |
12 ms |
2048 KB |
Output is correct |
22 |
Correct |
11 ms |
2048 KB |
Output is correct |
23 |
Correct |
11 ms |
2048 KB |
Output is correct |
24 |
Correct |
12 ms |
2000 KB |
Output is correct |
25 |
Correct |
12 ms |
2048 KB |
Output is correct |
26 |
Correct |
12 ms |
2048 KB |
Output is correct |
27 |
Correct |
11 ms |
2048 KB |
Output is correct |
28 |
Correct |
12 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
15884 KB |
Output is correct |
2 |
Correct |
88 ms |
17124 KB |
Output is correct |
3 |
Correct |
9 ms |
1792 KB |
Output is correct |
4 |
Correct |
75 ms |
15672 KB |
Output is correct |
5 |
Correct |
132 ms |
18768 KB |
Output is correct |
6 |
Correct |
111 ms |
18628 KB |
Output is correct |
7 |
Correct |
94 ms |
17860 KB |
Output is correct |
8 |
Correct |
98 ms |
17848 KB |
Output is correct |
9 |
Correct |
106 ms |
18628 KB |
Output is correct |
10 |
Correct |
108 ms |
18744 KB |
Output is correct |
11 |
Correct |
98 ms |
18684 KB |
Output is correct |
12 |
Correct |
113 ms |
18732 KB |
Output is correct |
13 |
Correct |
107 ms |
18756 KB |
Output is correct |
14 |
Correct |
115 ms |
18816 KB |
Output is correct |
15 |
Correct |
117 ms |
18628 KB |
Output is correct |
16 |
Correct |
109 ms |
18788 KB |
Output is correct |
17 |
Correct |
101 ms |
18520 KB |
Output is correct |
18 |
Correct |
105 ms |
18344 KB |
Output is correct |
19 |
Correct |
107 ms |
18588 KB |
Output is correct |
20 |
Correct |
101 ms |
18364 KB |
Output is correct |
21 |
Correct |
91 ms |
18448 KB |
Output is correct |
22 |
Correct |
107 ms |
18348 KB |
Output is correct |
23 |
Correct |
82 ms |
15876 KB |
Output is correct |
24 |
Correct |
91 ms |
15884 KB |
Output is correct |
25 |
Correct |
89 ms |
16300 KB |
Output is correct |
26 |
Correct |
89 ms |
16192 KB |
Output is correct |
27 |
Correct |
103 ms |
17256 KB |
Output is correct |
28 |
Correct |
102 ms |
17280 KB |
Output is correct |
29 |
Correct |
97 ms |
17112 KB |
Output is correct |
30 |
Correct |
97 ms |
17212 KB |
Output is correct |
31 |
Correct |
86 ms |
15892 KB |
Output is correct |
32 |
Correct |
95 ms |
15844 KB |
Output is correct |
33 |
Correct |
99 ms |
16264 KB |
Output is correct |
34 |
Correct |
80 ms |
16292 KB |
Output is correct |
35 |
Correct |
99 ms |
17160 KB |
Output is correct |
36 |
Correct |
113 ms |
17224 KB |
Output is correct |
37 |
Correct |
98 ms |
17140 KB |
Output is correct |
38 |
Correct |
102 ms |
17152 KB |
Output is correct |
39 |
Correct |
99 ms |
17112 KB |
Output is correct |
40 |
Correct |
96 ms |
17128 KB |
Output is correct |
41 |
Correct |
96 ms |
17724 KB |
Output is correct |
42 |
Correct |
103 ms |
17844 KB |
Output is correct |
43 |
Correct |
124 ms |
17724 KB |
Output is correct |
44 |
Correct |
105 ms |
17724 KB |
Output is correct |
45 |
Correct |
98 ms |
17832 KB |
Output is correct |
46 |
Correct |
102 ms |
17912 KB |
Output is correct |
47 |
Correct |
95 ms |
16836 KB |
Output is correct |
48 |
Correct |
93 ms |
17008 KB |
Output is correct |
49 |
Correct |
107 ms |
16704 KB |
Output is correct |
50 |
Correct |
95 ms |
17028 KB |
Output is correct |
51 |
Correct |
87 ms |
16020 KB |
Output is correct |
52 |
Correct |
99 ms |
16112 KB |
Output is correct |
53 |
Correct |
86 ms |
16004 KB |
Output is correct |
54 |
Correct |
120 ms |
16072 KB |
Output is correct |
55 |
Correct |
84 ms |
16076 KB |
Output is correct |
56 |
Correct |
102 ms |
16060 KB |
Output is correct |
57 |
Correct |
98 ms |
16072 KB |
Output is correct |
58 |
Correct |
93 ms |
16152 KB |
Output is correct |
59 |
Correct |
92 ms |
16344 KB |
Output is correct |
60 |
Correct |
89 ms |
16240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
15812 KB |
Output is correct |
2 |
Correct |
110 ms |
16944 KB |
Output is correct |
3 |
Correct |
10 ms |
1792 KB |
Output is correct |
4 |
Correct |
89 ms |
15636 KB |
Output is correct |
5 |
Correct |
100 ms |
18884 KB |
Output is correct |
6 |
Correct |
107 ms |
18828 KB |
Output is correct |
7 |
Correct |
82 ms |
17868 KB |
Output is correct |
8 |
Correct |
88 ms |
17876 KB |
Output is correct |
9 |
Correct |
122 ms |
18652 KB |
Output is correct |
10 |
Correct |
130 ms |
18780 KB |
Output is correct |
11 |
Correct |
117 ms |
18580 KB |
Output is correct |
12 |
Correct |
102 ms |
18836 KB |
Output is correct |
13 |
Correct |
110 ms |
18704 KB |
Output is correct |
14 |
Correct |
94 ms |
18816 KB |
Output is correct |
15 |
Correct |
105 ms |
18748 KB |
Output is correct |
16 |
Correct |
118 ms |
18704 KB |
Output is correct |
17 |
Correct |
98 ms |
18492 KB |
Output is correct |
18 |
Correct |
104 ms |
18476 KB |
Output is correct |
19 |
Correct |
98 ms |
18344 KB |
Output is correct |
20 |
Correct |
108 ms |
18468 KB |
Output is correct |
21 |
Correct |
96 ms |
18500 KB |
Output is correct |
22 |
Correct |
103 ms |
18460 KB |
Output is correct |
23 |
Correct |
83 ms |
16064 KB |
Output is correct |
24 |
Correct |
82 ms |
15828 KB |
Output is correct |
25 |
Correct |
80 ms |
16268 KB |
Output is correct |
26 |
Correct |
86 ms |
16192 KB |
Output is correct |
27 |
Correct |
93 ms |
17300 KB |
Output is correct |
28 |
Correct |
88 ms |
17288 KB |
Output is correct |
29 |
Correct |
104 ms |
17240 KB |
Output is correct |
30 |
Correct |
97 ms |
17224 KB |
Output is correct |
31 |
Correct |
80 ms |
15884 KB |
Output is correct |
32 |
Correct |
88 ms |
15876 KB |
Output is correct |
33 |
Correct |
79 ms |
16312 KB |
Output is correct |
34 |
Correct |
95 ms |
16388 KB |
Output is correct |
35 |
Correct |
101 ms |
16956 KB |
Output is correct |
36 |
Correct |
100 ms |
17092 KB |
Output is correct |
37 |
Correct |
95 ms |
17056 KB |
Output is correct |
38 |
Correct |
106 ms |
17120 KB |
Output is correct |
39 |
Correct |
93 ms |
16956 KB |
Output is correct |
40 |
Correct |
91 ms |
17088 KB |
Output is correct |
41 |
Correct |
93 ms |
17776 KB |
Output is correct |
42 |
Correct |
100 ms |
17860 KB |
Output is correct |
43 |
Correct |
110 ms |
17712 KB |
Output is correct |
44 |
Correct |
91 ms |
17764 KB |
Output is correct |
45 |
Correct |
103 ms |
17752 KB |
Output is correct |
46 |
Correct |
103 ms |
17860 KB |
Output is correct |
47 |
Correct |
95 ms |
17184 KB |
Output is correct |
48 |
Correct |
107 ms |
16876 KB |
Output is correct |
49 |
Correct |
97 ms |
16768 KB |
Output is correct |
50 |
Correct |
102 ms |
16940 KB |
Output is correct |
51 |
Correct |
87 ms |
16132 KB |
Output is correct |
52 |
Correct |
98 ms |
16060 KB |
Output is correct |
53 |
Correct |
89 ms |
16096 KB |
Output is correct |
54 |
Correct |
81 ms |
16136 KB |
Output is correct |
55 |
Correct |
101 ms |
16108 KB |
Output is correct |
56 |
Correct |
89 ms |
16324 KB |
Output is correct |
57 |
Correct |
81 ms |
16104 KB |
Output is correct |
58 |
Correct |
87 ms |
16236 KB |
Output is correct |
59 |
Correct |
89 ms |
16284 KB |
Output is correct |
60 |
Correct |
91 ms |
16120 KB |
Output is correct |