#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include "incursion.h"
using namespace std;
typedef long long ll;
const ll INF = 0x3fffffffffffffff;
int d[45009];
bool ch[45009];
vector<int> graph[45009];
bool mar[6] = {0, 0, 1, 1, 0, 1};
void dfs(int v){
ch[v] = 1;
for(int i=0; i<graph[v].size(); i++){
int u = graph[v][i];
if(ch[u])
continue;
d[u] = d[v] + 1;
dfs(u);
}
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
int n = (int)F.size() + 1, i;
for(i=0; i<n-1; i++){
graph[F[i].first].push_back(F[i].second);
graph[F[i].second].push_back(F[i].first);
}
dfs(safe);
vector<int> ret(n);
for(i=0; i<n; i++){
ret[i] = mar[d[i+1] % 6];
if(graph[i+1].size() == 1){
if(safe != i+1 && safe != graph[i+1][0])
ret[i] = 1;
else
ret[i] = 0;
}
}
return ret;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
int n = (int)F.size() + 1, i, j;
int cor = 0;
for(i=1; i<=n; i++){
graph[i].clear();
ch[i] = 0;
}
for(i=0; i<n-1; i++){
graph[F[i].first].push_back(F[i].second);
graph[F[i].second].push_back(F[i].first);
}
if(graph[curr].size() == 2){
int c1 = visit(graph[curr][0]);
int c2 = visit(curr);
int c3 = visit(graph[curr][1]);
visit(curr);
if(c1 + c2 + c3 == 0)
return;
vector<int> colors;
colors.push_back(t);
vector<int> st;
st.push_back(curr);
int v = curr;
for(i=0; i<10; i++){
ch[v] = 1;
for(j=0; j<graph[v].size(); j++){
if(!ch[graph[v][j]]){
st.push_back(graph[v][j]);
colors.push_back(visit(graph[v][j]));
v= graph[v][j];
break;
}
}
if(j == graph[v].size()){
if(colors.back() == 0)
return;
else
break;
}
}
while(1){
st.pop_back();
if(st.empty())
break;
visit(st.back());
}
memset(ch, 0, sizeof(ch));
if(colors.size() != 11){
cor = 1;
for(i=0; i+2<colors.size(); i++){
if(colors[i] + colors[i+1] + colors[i+2] == 0)
cor = 0;
}
}
else{
bool flag = 0;
for(i=0; i+2<colors.size(); i++){
if(colors[i] + colors[i+1] + colors[i+2] == 0)
cor = 0, flag = 1;
}
if(flag==0){
for(i=0; i<11; i++){
if(colors[i] == 0)
break;
}
for(i++; i<11; i++){
if(colors[i] == 1)
break;
}
int cnt = 0, cnt2 = 0;
for(; i<11; i++){
if(colors[i] == 1)
cnt++;
else
break;
}
for(; i<11; i++){
if(colors[i] == 0)
cnt2++;
else
break;
}
//printf("cnt=%d cnt2=%d\n", cnt, cnt2);
if(cnt2>=3 || cnt == cnt2)
cor = 0;
else
cor = 1;
}
}
}
memset(ch, 0, sizeof(ch));
int zero = 1 - t;
ch[curr] = 1;
ch[graph[curr][cor]] = 1;
int v = graph[curr][cor];
if(visit(v) == 0)
zero++;
else
zero = 0;
while(1){
ch[v] = 1;
//printf("v=%d zero=%d\n", v, zero);
if(zero == 3 || graph[v].size() == 1){
//printf("v=%d zero=%d\n", v, zero);
if(graph[v].size()==1 && zero != 0 && zero != 3)
return;
for(int j=0; j<graph[v].size(); j++){
if(ch[graph[v][j]]){
visit(graph[v][j]);
return;
}
}
}
for(int i=0; i<graph[v].size(); i++){
if(ch[graph[v][i]])
continue;
if(visit(graph[v][i]) == 0)
zero++;
else
zero = 0;
v = graph[v][i];
}
}
}
Compilation message
incursion.cpp: In function 'void dfs(int)':
incursion.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:72:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(j=0; j<graph[v].size(); j++){
| ~^~~~~~~~~~~~~~~~
incursion.cpp:80:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | if(j == graph[v].size()){
| ~~^~~~~~~~~~~~~~~~~~
incursion.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(i=0; i+2<colors.size(); i++){
| ~~~^~~~~~~~~~~~~~
incursion.cpp:103:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(i=0; i+2<colors.size(); i++){
| ~~~^~~~~~~~~~~~~~
incursion.cpp:153:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int j=0; j<graph[v].size(); j++){
| ~^~~~~~~~~~~~~~~~
incursion.cpp:160:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
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);
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2816 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
9584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
7332 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2816 KB |
Correct |
| 2 |
Execution timed out |
3062 ms |
9584 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
