結果

問題 No.1153 ねこちゃんゲーム
ユーザー CinnamorollCinnamoroll
提出日時 2020-08-08 03:06:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,833 bytes
コンパイル時間 1,870 ms
コンパイル使用メモリ 178,072 KB
実行使用メモリ 66,792 KB
最終ジャッジ日時 2024-09-25 05:43:49
合計ジャッジ時間 21,647 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
12,672 KB
testcase_01 AC 7 ms
12,640 KB
testcase_02 WA -
testcase_03 AC 9 ms
12,648 KB
testcase_04 AC 7 ms
12,776 KB
testcase_05 AC 8 ms
12,576 KB
testcase_06 AC 8 ms
12,760 KB
testcase_07 AC 320 ms
20,008 KB
testcase_08 AC 229 ms
20,128 KB
testcase_09 AC 333 ms
20,044 KB
testcase_10 AC 238 ms
20,196 KB
testcase_11 AC 324 ms
20,160 KB
testcase_12 AC 340 ms
19,900 KB
testcase_13 AC 248 ms
20,028 KB
testcase_14 AC 336 ms
20,160 KB
testcase_15 AC 238 ms
20,080 KB
testcase_16 AC 343 ms
20,000 KB
testcase_17 AC 324 ms
19,960 KB
testcase_18 AC 240 ms
20,024 KB
testcase_19 AC 343 ms
20,040 KB
testcase_20 AC 249 ms
20,156 KB
testcase_21 AC 330 ms
20,080 KB
testcase_22 AC 337 ms
20,008 KB
testcase_23 AC 245 ms
20,120 KB
testcase_24 AC 323 ms
19,996 KB
testcase_25 AC 247 ms
20,080 KB
testcase_26 AC 302 ms
20,108 KB
testcase_27 AC 428 ms
65,696 KB
testcase_28 AC 317 ms
66,792 KB
testcase_29 AC 418 ms
62,436 KB
testcase_30 AC 316 ms
61,904 KB
testcase_31 AC 417 ms
44,732 KB
testcase_32 AC 219 ms
25,436 KB
testcase_33 AC 170 ms
25,696 KB
testcase_34 AC 221 ms
25,444 KB
testcase_35 AC 165 ms
25,436 KB
testcase_36 AC 210 ms
25,432 KB
testcase_37 AC 135 ms
25,356 KB
testcase_38 AC 122 ms
23,040 KB
testcase_39 AC 128 ms
23,160 KB
testcase_40 AC 135 ms
25,604 KB
testcase_41 AC 122 ms
27,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// warm heart, wagging tail,and a smile just for you!
//                                                                     ███████████
//                                                                   ███╬╬╬╬╬╬╬╬╬╬███
//                                                                ███╬╬╬╬╬████╬╬╬╬╬╬███
//                                            ███████████       ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
//                                      █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
//                               ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
//                             ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
//                           ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
//                         ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
//                       ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
//                     ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
//                 ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
//     █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
//   ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
//   ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
//       ██████████████  ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
//                         ███████                           █████  ███████████████████  
//
#include "bits/stdc++.h"
using namespace std;
#define INF (1<<30)
#define LINF (1LL<<60)
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR2(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define RFOR2(i,a,b) for(int i = (b);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define REP2(i,n)  FOR2(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define RREP2(i,n) RFOR2(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl
#define SP << " " << 
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b) {a=b; return true;} else return false;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b) {a=b; return true;} else return false;}
#define MSB(x) (63-__builtin_clzll(x))
#define pcnt(x) (__builtin_popcountll(x))
#define parity(i,j) (i&(1LL<<j))
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

const int N = 202020;
vector<int> edge[N], a(N,0), dp(N), p(N,0);

template<typename T>
vector<T> compress(vector<T> v){
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  return v;
}

int mex(vector<int> &a){
  if(!a.size()) return 0;
  vector<int> b = compress(a);
  int ng = b.size()+1, ok = 0;
  while (abs(ng-ok)>1) {
    int mid = ng+(ok-ng)/2;
    int x = lower_bound(b.begin(),b.end(),mid) - b.begin();
    (x==mid?ok:ng) = mid;
  }
  return ok;
}

void dfs(int no, int par = -1){
  vec b;
  for(int to: edge[no]){
    if(to==par) continue;
    dfs(to,no);
    b.push_back(dp[to]);
  }
  dp[no] = mex(b);
}

int g = 0, ans1, ans2;
void dfs2(int no, int par, bool flag){
  vec b, cnt(edge[no].size()+2,0);
  for(int to:edge[no]) b.push_back(dp[to]), cnt[min(dp[to],(int)cnt.size()-1)]++;
  int m = mex(b);
  if(p[no]&&!flag) g ^= m;
  for(int to:edge[no]){
    if(to==par) continue;
    int tmp = dp[no];
    if(dp[to] < cnt.size() && cnt[dp[to]]==1) dp[no] = min(dp[to],m);
    else dp[no] = m;
    if(flag && a[no]){
      //debug(m); debug(g);
      if((g^m^dp[to])==0) ans1 = a[no], ans2 = to+1;
    }
    dfs2(to,no,flag);
    dp[no] = tmp;
  }
}

void solve(){
  int N,M;
  cin >> N >> M;

  REP(i,M){
    int x; cin >> x;
    a[x-1] = i+1;
    p[x-1] ^= 1;
  }
  
  REP(_,N-1){
    int x,y;
    cin >> x >> y;
    x--; y--;
    edge[x].emplace_back(y);
    edge[y].emplace_back(x);
  }

  dfs(0);
  // REP(i,N) cout << dp[i] << " "; cout << endl;
  dfs2(0,-1,false);

  // debug(g);

  if(!g){
    //assert(false);
    cout << -1 SP -1 << endl;
  }
  else{
    //assert(false);
    //cout << -1 SP -1 << endl;
    dfs2(0,-1,true);
    cout << ans1 SP ans2 << endl;
  }

}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int T = 1;
  // cin >> T;

  while(T--) solve();

  return 0;
}
0