#include "Joi.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 10000;
const int MAX_M = 20000;
vector<int> grpa[MAX_N+1];
vector<int> grp2[MAX_N+1];
int nmb[MAX_N+1];
int pa[MAX_N+1];
int chc[MAX_N+1];
int dgr[MAX_N+1];
set<int> s;
int find_leafa(int x){
for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
dgr[*it] = 0;
}
for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
int k = (*it);
if(k==0) continue;
if(chc[pa[k]]){
dgr[pa[k]]++;
dgr[k]++;
}
}
for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
int k = (*it);
if(dgr[k]==1 && k!=x) return k;
}
}
void dfsa(int x){
int t = -1;
if(s.size()==60){
int lf = find_leafa(pa[x]);
t = lf;
s.erase(lf);
chc[lf] = false;
nmb[x] = nmb[lf];
chc[x] = true;
s.insert(x);
}else if(s.size()==59){
s.insert(x);
chc[x] = true;
int cnt = 0;
for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
nmb[*it] = cnt;
cnt++;
}
}else{
s.insert(x);
chc[x] = true;
}
for(int i=0; i<grpa[x].size(); i++){
if(grpa[x][i]==pa[x]) continue;
pa[grpa[x][i]] = x;
dfsa(grpa[x][i]);
}
if(t!=-1){
s.erase(x);
s.insert(t);
chc[t] = true;
chc[x] = false;
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for(int i=0; i<M; i++){
grpa[A[i]].pb(B[i]); grpa[B[i]].pb(A[i]);
}
dfsa(0);
ll t = 1;
for(int i=0; i<N; i++){
MessageBoard(i, ((t & X)>0));
//cout<<i<<" "<<nmb[i]<<" "<<((t & X)>0)<<endl;
t*=2;
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 10000;
const int MAX_M = 20000;
vector<int> gp[MAX_N+1];
vector<int> gp2[MAX_N+1];
int num[MAX_N+1];
int p[MAX_N+1];
int chk[MAX_N+1];
int deg[MAX_N+1];
set<int> st;
int find_leaf(int x){
for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
deg[*it] = 0;
}
for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
int k = (*it);
if(k==0) continue;
if(chk[p[k]]){
deg[p[k]]++;
deg[k]++;
}
}
for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
int k = (*it);
if(deg[k]==1 && k!=x) return k;
}
}
bool found = false;
int pos;
void dfs(int x){
int t = -1;
if(st.size()==60){
int lf = find_leaf(p[x]);
t = lf;
st.erase(lf);
chk[lf] = false;
num[x] = num[lf];
chk[x] = true;
st.insert(x);
if(x==pos){
found = true;
return;
}
}else if(st.size()==59){
st.insert(x);
chk[x] = true;
int cnt = 0;
for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
num[*it] = cnt;
cnt++;
}
if(st.find(pos)!=st.end()){
found = true;
return;
}
}else{
st.insert(x);
chk[x] = true;
}
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]==p[x]) continue;
p[gp[x][i]] = x;
dfs(gp[x][i]);
if(found) return;
}
if(t!=-1){
st.erase(x);
st.insert(t);
chk[t] = true;
chk[x] = false;
}
}
bool vst[MAX_N+1];
int ans[100];
void calc(int x){
vst[x] = true;
for(int i=0; i<gp[x].size(); i++){
if(chk[gp[x][i]] && !vst[gp[x][i]]){
int t = Move(gp[x][i]);
ans[num[gp[x][i]]] = t;
calc(gp[x][i]);
Move(x);
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
pos = P;
for(int i=0; i<M; i++){
gp[A[i]].pb(B[i]); gp[B[i]].pb(A[i]);
}
dfs(0);
ans[num[P]] = V;
calc(P);
ll answer=0;
ll t = 1;
for(int i=0; i<60; i++){
answer += (ll)ans[i] * t;
t*=2;
}
//cout<<answer;
return answer;
}
Compilation message
Joi.cpp: In function 'void dfsa(int)':
Joi.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<grpa[x].size(); i++){
~^~~~~~~~~~~~~~~
Joi.cpp: In function 'int find_leafa(int)':
Joi.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
Ioi.cpp: In function 'void dfs(int)':
Ioi.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
Ioi.cpp: In function 'void calc(int)':
Ioi.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[x].size(); i++){
~^~~~~~~~~~~~~
Ioi.cpp: In function 'int find_leaf(int)':
Ioi.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1884 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1878 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1652 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1652 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
1780 KB |
Wrong Answer [7] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1958 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1968 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
