Submission #520832

#TimeUsernameProblemLanguageResultExecution timeMemory
520832tube5429Usmjeri (COCI17_usmjeri)C++14
140 / 140
434 ms84704 KiB
#include<bits/stdc++.h> using namespace std; #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(e,a) for(auto &e : (a)) #define sz(v) (int)(v).size() #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define rsz resize #define pb push_back #define f first #define s second #define pf push_front #define ft front() #define bk back() #define eb emplace_back #define lb lower_bound #define ub upper_bound #define tcT template<class T #define tcTU tcT, class U #define nl "\n" using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vb = vector<bool>; using pi = pair<int,int>; using vpi = vector<pi>; using str = string; using vs = vector<str>; using db = double; using pl = pair<ll,ll>; using pd = pair<db,db>; tcT> using V = vector<T>; tcT> using pqg = priority_queue<T,vector<T>,greater<T>>; tcTU> using PR = pair<T,U>; const int MOD = 1e9+7; const ll INF = 1e18; const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); } constexpr bool onbit(int msk, int i) { return msk>>i&1; } constexpr ll p2(int x) { return 1LL<<x; } constexpr int pct(int x) { return __builtin_popcount(x); } constexpr int lg2(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }; //int only template<int N> constexpr ll pow10 = pow10<N-1> * 10; template<> constexpr ll pow10<0> = 1; tcT> bool ckmin(T&a, const T&b) { return b < a ? a = b,1 : 0; } tcT> bool ckmax(T&a, const T&b) { return b > a ? a = b,1 : 0; } ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } tcTU> T fstTrue(T lo, T hi, U f) { hi++; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; } tcTU> T lstTrue(T lo, T hi, U f) { lo--; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; } tcT> void remDup(V<T> &v) { sort(all(v)); v.erase(unique(all(v)), end(v)); } void DBG() { cerr << "]\n"; } template<class H, class... T> void DBG(H h, T... t) { cerr << h; if(sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif // LOCAL void setPrec() { cout << fixed << setprecision(16); } void setIO(string NAME = "") { cin.tie(0)->sync_with_stdio(0); setPrec(); if(sz(NAME)) { freopen((NAME + ".in").c_str(),"r",stdin); freopen((NAME + ".out").c_str(),"w",stdout); } } template<int SZ, int LG> struct Tree { int N, par[LG][SZ], dep[SZ]; vi adj[SZ]; void init(int _N) { N = _N; F0R(i,N) adj[i].clear(); } void ae(int u, int v) { adj[u].pb(v), adj[v].pb(u); } void gen(int R = 0) { dep[par[0][R] = R] = 0; dfs(R); } void dfs(int x = 0) { FOR(i,1,LG) par[i][x] = par[i-1][par[i-1][x]]; each(y, adj[x]) if(y!=par[0][x]) dep[y] = dep[par[0][y] = x] + 1, dfs(y); } int jmp(int x, int d) { F0R(i,LG) if(onbit(d,i)) x = par[i][x]; return x; } int lca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); x = jmp(x, dep[x] - dep[y]); if(x == y) return x; R0F(i,LG) if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y]; return par[0][x]; } int dist(int x, int y) { return dep[x] + dep[y] - (dep[lca(x,y)]<<1); } }; const int MX = 3e5+5; int N, M, hi[MX], color[MX]; vpi adj[MX]; Tree<MX, lg2(MX)> tr; int connect(int u) { each(v, tr.adj[u]) if(v!=tr.par[0][u]) { int tmp = connect(v); ckmin(hi[u], tmp); if(tmp < tr.dep[u]) { adj[u].pb({v,0}); adj[v].pb({u,0}); } } return hi[u]; } bool dfs(int x, int c) { if(~color[x]) return color[x] == c; color[x] = c; each(y, adj[x]) if(!dfs(y.f, c^y.s)) return false; return true; } void solve() { cin>>N>>M; tr.init(N+5); REP(N-1) { int u,v; cin>>u>>v, --u, --v; tr.ae(u,v); } tr.gen(); F0R(i,N) hi[i] = tr.dep[i]; REP(M) { int a,b; cin>>a>>b, --a, --b; int c = tr.lca(a,b); ckmin(hi[a], tr.dep[c]); ckmin(hi[b], tr.dep[c]); if(c!=a && c!=b) { adj[a].pb({b,1}); adj[b].pb({a,1}); } } connect(0); ll ans = 1; FOR(i,1,N) if(color[i] == -1) { if(!dfs(i, 0)) { cout << "0\n"; return; } ans = (ans*2)%MOD; } cout << ans << "\n"; } int main() { setIO(); memset(color, -1, sizeof color); int t=1; //cin>>t; while(t-->0) { solve(); } return 0; }

Compilation message (stderr)

usmjeri.cpp: In function 'void setIO(std::string)':
usmjeri.cpp:96:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   freopen((NAME + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:97:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   freopen((NAME + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...