Submission #1750275
Source Code Expand
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int N = 100005 ;
using namespace std ;
int n, d[N << 1] ;
map <int, map<int, int> > cnt ;
multiset <int> E[N] ;
set <pair<int, int> > Q ;
void add(int x, int y) {
E[x].insert(y) ;
int tmp = ++ cnt[x][y] ;
if (tmp > 1) Q.insert(make_pair(min(x, y), max(x, y))) ;
}
void del(int x, int y) {
E[x].erase(E[x].find(y)) ;
int tmp = -- cnt[x][y] ;
if (tmp < 2) Q.erase(make_pair(min(x, y), max(x, y))) ;
}
bool check() {
rep(k, 1, n - 1) {
if (Q.empty()) return false ;
pair <int, int> u = *Q.begin() ;
Q.erase(u) ;
int x = u.first, y = u.second ;
del(x, y), del(x, y), del(y, x), del(y, x) ;
if (E[x].size() > E[y].size()) swap(x, y) ;
std :: multiset <int> :: iterator it ;
d[0] = 0 ;
for (it = E[x].begin() ; it != E[x].end() ; it ++) {
int v = *it ;
add(y, v), add(v, y) ;
d[++ d[0]] = v ;
}
rep(i, 1, d[0]) {
del(x, d[i]), del(d[i], x) ;
}
}
return true ;
}
int main() {
scanf("%d", &n) ;
int x, y ;
rep(i, 1, n - 1) {
scanf("%d%d", &x, &y) ;
add(x, y), add(y, x) ;
}
rep(i, 1, n - 1) {
scanf("%d%d", &x, &y) ;
add(x, y), add(y, x) ;
}
if (check()) printf("YES\n") ;
else printf("NO\n") ;
return 0 ;
}
Submission Info
Submission Time |
|
Task |
E - Blue and Red Tree |
User |
mjy0724 |
Language |
C++14 (GCC 5.4.1) |
Score |
1400 |
Code Size |
1442 Byte |
Status |
AC |
Exec Time |
1054 ms |
Memory |
54784 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:53:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n) ;
^
./Main.cpp:56:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y) ;
^
./Main.cpp:60:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y) ;
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1400 / 1400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
3 ms |
4992 KB |
in10.txt |
AC |
385 ms |
51840 KB |
in11.txt |
AC |
860 ms |
50048 KB |
in12.txt |
AC |
910 ms |
50048 KB |
in13.txt |
AC |
903 ms |
50048 KB |
in14.txt |
AC |
885 ms |
50048 KB |
in15.txt |
AC |
879 ms |
50048 KB |
in16.txt |
AC |
894 ms |
50048 KB |
in17.txt |
AC |
867 ms |
50048 KB |
in18.txt |
AC |
885 ms |
50048 KB |
in19.txt |
AC |
869 ms |
50048 KB |
in2.txt |
AC |
3 ms |
4992 KB |
in20.txt |
AC |
870 ms |
50048 KB |
in21.txt |
AC |
859 ms |
50176 KB |
in22.txt |
AC |
864 ms |
50176 KB |
in23.txt |
AC |
851 ms |
50176 KB |
in24.txt |
AC |
859 ms |
50176 KB |
in25.txt |
AC |
867 ms |
50176 KB |
in26.txt |
AC |
893 ms |
50048 KB |
in27.txt |
AC |
878 ms |
50048 KB |
in28.txt |
AC |
885 ms |
50048 KB |
in29.txt |
AC |
879 ms |
50048 KB |
in3.txt |
AC |
3 ms |
4992 KB |
in30.txt |
AC |
914 ms |
50048 KB |
in31.txt |
AC |
984 ms |
53120 KB |
in32.txt |
AC |
1001 ms |
53120 KB |
in33.txt |
AC |
977 ms |
53120 KB |
in34.txt |
AC |
978 ms |
53120 KB |
in35.txt |
AC |
985 ms |
53120 KB |
in36.txt |
AC |
980 ms |
53120 KB |
in37.txt |
AC |
982 ms |
53120 KB |
in38.txt |
AC |
919 ms |
52992 KB |
in39.txt |
AC |
906 ms |
53120 KB |
in4.txt |
AC |
387 ms |
51840 KB |
in40.txt |
AC |
853 ms |
54784 KB |
in41.txt |
AC |
1031 ms |
53120 KB |
in42.txt |
AC |
1054 ms |
53120 KB |
in43.txt |
AC |
1031 ms |
53120 KB |
in44.txt |
AC |
1019 ms |
53120 KB |
in45.txt |
AC |
1029 ms |
53120 KB |
in46.txt |
AC |
905 ms |
53120 KB |
in47.txt |
AC |
851 ms |
53120 KB |
in5.txt |
AC |
387 ms |
51840 KB |
in6.txt |
AC |
907 ms |
53120 KB |
in7.txt |
AC |
393 ms |
51840 KB |
in8.txt |
AC |
386 ms |
51840 KB |
in9.txt |
AC |
389 ms |
51840 KB |
sample1.txt |
AC |
3 ms |
4992 KB |
sample2.txt |
AC |
3 ms |
4992 KB |
sample3.txt |
AC |
3 ms |
4992 KB |