Submission #635712

#TimeUsernameProblemLanguageResultExecution timeMemory
635712IWTIMUsmjeri (COCI17_usmjeri)C++14
140 / 140
497 ms105384 KiB
# include <bits/stdc++.h> using namespace std; using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pii = pair<int,int>; using pl = pair<ll,ll>; using pd = pair<db,db>; #define mp make_pair #define f first #define s second #define tcT template<class T #define tcTU tcT, class U // ^ lol this makes everything look weird but I'll try it tcT> using V = vector<T>; tcT, size_t SZ> using AR = array<T,SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pii>; using vpl = V<pl>; using vpd = V<pd>; // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) const int MOD = 998244353; const int MX = 2e5+5; const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!! mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>; struct DSU { vi e; void init(int N) { e = vi(N,-1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool sameSet(int a, int b) { return get(a) == get(b); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { // union by size x = get(x), y = get(y); if (x == y) return 0; if (e[x] > e[y]) swap(x,y); e[x] += e[y]; e[y] = x; return 1; } }; /* inline namespace Helpers { //////////// is_iterable // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable // this gets used only when we can call begin() and end() on that type tcT, class = void> struct is_iterable : false_type {}; tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>())) > > : true_type {}; tcT> constexpr bool is_iterable_v = is_iterable<T>::value; //////////// is_readable tcT, class = void> struct is_readable : false_type {}; tcT> struct is_readable<T, typename std::enable_if_t< is_same_v<decltype(cin >> declval<T&>()), istream&> > > : true_type {}; tcT> constexpr bool is_readable_v = is_readable<T>::value; //////////// is_printable // // https://nafe.es/posts/2020-02-29-is-printable/ tcT, class = void> struct is_printable : false_type {}; tcT> struct is_printable<T, typename std::enable_if_t< is_same_v<decltype(cout << declval<T>()), ostream&> > > : true_type {}; tcT> constexpr bool is_printable_v = is_printable<T>::value; }*/ using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pii = pair<int,int>; using pl = pair<ll,ll>; using pd = pair<db,db>; #define mp make_pair #define f first #define s second #define tcT template<class T #define tcTU tcT, class U // ^ lol this makes everything look weird but I'll try it tcT> using V = vector<T>; tcT, size_t SZ> using AR = array<T,SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pii>; using vpl = V<pl>; using vpd = V<pd>; // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>; /* inline namespace Helpers { //////////// is_iterable // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable // this gets used only when we can call begin() and end() on that type tcT, class = void> struct is_iterable : false_type {}; tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>())) > > : true_type {}; tcT> constexpr bool is_iterable_v = is_iterable<T>::value; //////////// is_readable tcT, class = void> struct is_readable : false_type {}; tcT> struct is_readable<T, typename std::enable_if_t< is_same_v<decltype(cin >> declval<T&>()), istream&> > > : true_type {}; tcT> constexpr bool is_readable_v = is_readable<T>::value; //////////// is_printable // // https://nafe.es/posts/2020-02-29-is-printable/ tcT, class = void> struct is_printable : false_type {}; tcT> struct is_printable<T, typename std::enable_if_t< is_same_v<decltype(cout << declval<T>()), ostream&> > > : true_type {}; tcT> constexpr bool is_printable_v = is_printable<T>::value; }*/ const int N = 3e5 + 5; int t,n,a[N],b[N],p[N],fix[N],fix1[N],sz[N],m, lv[N]; int x[N],y[N]; vector <int> v[N],con[N],v1[N]; int par[N][20],tin, in[N],out[N],mn[N]; multiset <int> s; int get_col(int a) { if (a == p[a]) return a; else return p[a] = get_col(p[a]); } void col(int a, int b) { a = get_col(a); b = get_col(b); if (a == b) return ; if (sz[a] < sz[b]) swap(a,b); p[b] = a; sz[a] += sz[b]; sz[b] = 0; } void init() { for (int i = 1; i <= n; i++) { p[i] = i; sz[i] = 1; } } void dfs(int a, int p) { lv[a] = lv[p] + 1; par[a][0] = p; tin++; in[a] = tin; for (int i = 1; i <= 18; i++) { if (par[a][i - 1]) par[a][i] = par[par[a][i - 1]][i - 1]; } for (int to : v[a]) { if (to == p) continue; dfs(to,a); } out[a] = tin; } int upper(int a, int b) { return (in[a] <= in[b] && out[a] >= out[b]); } int lca(int a, int b) { if (upper(a,b)) return a; for (int i = 18; i >= 0; i--) { if (par[a][i] && !upper(par[a][i],b)) a = par[a][i]; } return par[a][0]; } void dfs1(int a, int p) { mn[a] = 1e9; for (int x : con[a]) mn[a] = min(mn[a], lv[x]); for (int to : v[a]) { if (to == p) continue; dfs1(to,a); if (p && mn[to] <= lv[p]) col(a,to); mn[a] = min(mn[a], mn[to]); } } void check(int a, int p) { fix1[a] = 1; for (int to : v1[a]) { if (to == p) continue; if (fix1[to]) { cout<<0<<"\n"; exit(0); } check(to, a); } } main() { std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; init(); for (int i = 1; i <= n - 1; i++) { int a, b; cin>>x[i]>>y[i]; v[x[i]].pb(y[i]); v[y[i]].pb(x[i]); } for (int i = 1; i <= m; i++) { cin>>a[i]>>b[i]; } dfs(1,0); for (int i = 1; i <= m; i++) { int lc = lca(a[i],b[i]); if (lv[a[i]] - lv[lc] >= 2) con[a[i]].pb(lc); if (lv[b[i]] - lv[lc] >= 2) con[b[i]].pb(lc); } dfs1(1,0); set <pii>ss; for (int i = 1; i <= m; i++) { int lc = lca(a[i],b[i]); if(lc == a[i] || lc == b[i]) continue; int aa = get_col(a[i]); int bb = get_col(b[i]); if (ss.count({aa,bb})) continue; ss.insert({aa,bb}); ss.insert({bb,aa}); v1[aa].pb(bb); v1[bb].pb(aa); if (get_col(a[i]) == get_col(b[i])) { cout<<0<<"\n"; exit(0); } } for (int i = 2; i <= n; i++) { if (!fix1[i]) { check(i, 0); } } for (int i = 1; i <= m; i++) { int lc = lca(a[i],b[i]); if (lc == a[i] || lc == b[i]) continue; col(a[i],b[i]); } set <int> st; for (int i = 2; i <= n; i++) { st.insert(get_col(i)); } long long x = 1, mod = 1e9 + 7; for (int i = 1; i <= (int)st.size(); i++) { x *= 2LL; x %= mod; } cout<<x<<"\n"; }

Compilation message (stderr)

usmjeri.cpp:252:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  252 | main() {
      | ^~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:257:10: warning: unused variable 'a' [-Wunused-variable]
  257 |      int a, b;
      |          ^
usmjeri.cpp:257:13: warning: unused variable 'b' [-Wunused-variable]
  257 |      int a, b;
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...