#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int uf[10100];
int f(int n)
{
return uf[n] == n ? n : uf[n] = f(uf[n]);
}
void u(int n, int m)
{
uf[f(n)] = f(m);
}
vector<int>link[10100];
vector<int>tt[10100];
bool cnt[10100][10100];
int bass[100100];
void dfs(int n, int p)
{
int i;
for (i = 0; i < tt[n].size(); i++)
{
if (tt[n][i] == n)
continue;
int j;
int r = 0;
for (j = 0; j < tt[n].size(); j++)
{
if (i == j)
continue;
if (cnt[tt[n][i]][tt[n][j]])
{
r++;
}
}
if (r == 1)
break;
}
int ers = tt[n][i];
for (i = 0; i < link[n].size(); i++)
{
if (link[n][i] == p)
continue;
int j;
if (tt[link[n][i]].size())
goto T;
for (j = 0; j < tt[n].size(); j++)
{
if (tt[n][j] != ers)
{
tt[link[n][i]].push_back(tt[n][j]);
}
}
bass[link[n][i]] = ers;
tt[link[n][i]].push_back(link[n][i]);
T:
dfs(link[n][i], n);
}
}
vector<int>fs;
void dfs2(int n, int p)
{
if (fs.size() == 60)
{
return;
}
int i;
bass[n] = fs.size();
fs.push_back(n);
for (i = 0; i < link[n].size(); i++)
{
if (link[n][i] == p)
continue;
dfs2(link[n][i], n);
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
memset(bass, -1, sizeof(bass));
int i;
for (i = 0; i < N; i++)
{
uf[i] = i;
}
for (i = 0; i < M; i++)
{
if (f(A[i]) != f(B[i]))
{
u(A[i], B[i]);
cnt[A[i]][B[i]] = true;
cnt[B[i]][A[i]] = true;
link[A[i]].push_back(B[i]);
link[B[i]].push_back(A[i]);
}
}
dfs2(0, -1);
for (i = 0; i < fs.size(); i++)
{
tt[fs[i]] = fs;
}
dfs(0, -1);
for (i = 0; i < N; i++)
{
MessageBoard(i, (int)((X >> (bass[i]))&1));
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
int uf[10100];
int f(int n)
{
return uf[n] == n ? n : uf[n] = f(uf[n]);
}
void u(int n, int m)
{
uf[f(n)] = f(m);
}
vector<int>link[10100];
vector<int>tt[10100];
bool cnt[10100][10100];
int bass[100100];
void dfs(int n, int p)
{
int i;
for (i = 0; i < tt[n].size(); i++)
{
if (tt[n][i] == n)
continue;
int j;
int r = 0;
for (j = 0; j < tt[tt[n][i]].size(); j++)
{
if (cnt[tt[n][i]][tt[tt[n][i]][j]])
{
r++;
}
}
if (r == 1)
break;
}
int ers = tt[n][i];
for (i = 0; i < link[n].size(); i++)
{
if (link[n][i] == p)
continue;
int j;
if (tt[link[n][i]].size())
goto T;
for (j = 0; j < tt[n].size(); j++)
{
if (tt[n][j] != ers)
{
tt[link[n][i]].push_back(tt[n][j]);
}
}
bass[link[n][i]] = ers;
tt[link[n][i]].push_back(link[n][i]);
T:
dfs(link[n][i], n);
}
}
vector<int>fs;
void dfs2(int n, int p)
{
if (fs.size() == 60)
{
return;
}
int i;
bass[n] = fs.size();
fs.push_back(n);
for (i = 0; i < link[n].size(); i++)
{
if (link[n][i] == p)
continue;
dfs2(link[n][i], n);
}
}
int ans[60];
bool ind[20010];
void dfs3(int n, int p)
{
int i;
for (i = 0; i < link[n].size(); i++)
{
if (link[n][i] == p)
continue;
if (!ind[link[n][i]])
continue;
ans[bass[link[n][i]]] = Move(link[n][i]);
dfs3(link[n][i], n);
Move(n);
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
memset(bass, -1, sizeof(bass));
int i;
for (i = 0; i < N; i++)
{
uf[i] = i;
}
for (i = 0; i < M; i++)
{
if (f(A[i]) != f(B[i]))
{
u(A[i], B[i]);
cnt[A[i]][B[i]] = true;
cnt[B[i]][A[i]] = true;
link[A[i]].push_back(B[i]);
link[B[i]].push_back(A[i]);
}
}
dfs2(0, -1);
for (i = 0; i < fs.size(); i++)
{
tt[fs[i]] = fs;
}
dfs(0, -1);
ans[bass[P]] = V;
for (i = 0; i < tt[P].size(); i++)
{
ind[tt[P][i]] = 1;
}
dfs3(P, -1);
long long rans = 0;
for (i = 0; i < 60; i++)
{
rans += (1LL << i) * ans[i];
}
return rans;
}
Compilation message
Joi.cpp: In function 'void {anonymous}::dfs(int, int)':
Joi.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (i = 0; i < tt[n].size(); i++)
| ~~^~~~~~~~~~~~~~
Joi.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (j = 0; j < tt[n].size(); j++)
| ~~^~~~~~~~~~~~~~
Joi.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (i = 0; i < link[n].size(); i++)
| ~~^~~~~~~~~~~~~~~~
Joi.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (j = 0; j < tt[n].size(); j++)
| ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void {anonymous}::dfs2(int, int)':
Joi.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (i = 0; i < link[n].size(); i++)
| ~~^~~~~~~~~~~~~~~~
Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:99:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (i = 0; i < fs.size(); i++)
| ~~^~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::dfs(int, int)':
Ioi.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (i = 0; i < tt[n].size(); i++)
| ~~^~~~~~~~~~~~~~
Ioi.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (j = 0; j < tt[tt[n][i]].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~
Ioi.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (i = 0; i < link[n].size(); i++)
| ~~^~~~~~~~~~~~~~~~
Ioi.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (j = 0; j < tt[n].size(); j++)
| ~~^~~~~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::dfs2(int, int)':
Ioi.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (i = 0; i < link[n].size(); i++)
| ~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void {anonymous}::dfs3(int, int)':
Ioi.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (i = 0; i < link[n].size(); i++)
| ~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:113:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (i = 0; i < fs.size(); i++)
| ~~^~~~~~~~~~~
Ioi.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (i = 0; i < tt[P].size(); i++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3080 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3592 KB |
Wrong Answer [7] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
126596 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3080 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3336 KB |
Wrong Answer [7] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
126296 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
126304 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
