| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1095618 |
2024-10-02T17:30:30 Z |
tfgs |
Usmjeri (COCI17_usmjeri) |
C++17 |
|
181 ms |
168784 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
#define f first
#define s second
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define len(x) (int)((x).size())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }
#define pct __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
constexpr int p2(int x) { return (int)1 << x; }
constexpr int bits(int x) { return x == 0 ? 0 : 31-clz(x); } // floor(log2(x))
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res {1};
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MInt {
i64 x;
constexpr MInt() : x {0} {}
constexpr MInt(i64 x) : x {norm(x % getMod())} {}
static inline i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
if (getMod() < (1ULL << 31)) {
x = x * rhs.x % int(getMod());
} else {
x = mul(x, rhs.x, getMod());
}
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v = 69;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
friend constexpr bool operator<(MInt lhs, MInt rhs) {
return lhs.val() < rhs.val();
}
};
template<>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 1000000007;
using Z = MInt<P>;
Z ans=1;
const int LOG=19;
V<vi>up,g;
V<V<array<int,2>>>queries;
vi mentions,dep,pseudo_map;
void init_lca(int u,int p){
up[u][0]=p;
for(int v:g[u])if(v!=p){
dep[v]=dep[u]+1;
init_lca(v,u);
}
for(int i=1;i<LOG;i++){
up[u][i]=up[u][i-1]==-1?-1:up[up[u][i-1]][i-1];
}
}
int jump(int u,int x){
for(int i=LOG-1;i>=0;i--)if(x&p2(i)){
u=up[u][i];
}
return u;
}
int get_lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
u=jump(u,dep[u]-dep[v]);
if(u!=v)u=jump(u,1);
return u;
}
int rec(int u,int p){
int ind=0;
vi unres;
for(int v:g[u])if(v!=p){
unres.pb(rec(v,u));
pseudo_map[v]=ind++;
}
unres.pb(mentions[u]);
pseudo_map[u]=ind;
V<vi>h(ind);
vi col(ind,-1);
for(auto[x,y]:queries[u]){
x=pseudo_map[x];
y=pseudo_map[y];
unres[x]--;
unres[y]--;
}
for(auto[x,y]:queries[u]){
if(x==u||y==u)continue;
x=pseudo_map[x];
y=pseudo_map[y];
h[x].pb(y);
h[y].pb(x);
}
int up_col=-1;
auto label_bip=[&](auto&&self,int u,int cur_col)->void{
col[u]=cur_col;
if(unres[u]){
if(up_col==-1)up_col=cur_col;
if(up_col!=cur_col){
ans=0;
}
}
for(int v:h[u]){
if(col[v]==-1)self(self,v,1^cur_col);
else if(col[v]==cur_col)ans=0;
}
};
for(int u=0;u<ind;u++)if(col[u]==-1){
label_bip(label_bip,u,0);
if(up_col==-1)ans*=2;
}
int ret=0;
for(int i=0;i<=ind;i++)ret+=unres[i];
return ret;
}
void solve() {
int n,q;cin>>n>>q;
g.resize(n);
dep.rsz(n);
mentions.rsz(n);
up.rsz(n,vi(LOG));
queries.rsz(n);
pseudo_map.rsz(n);
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;u--;v--;
g[u].pb(v);g[v].pb(u);
}
init_lca(0,-1);
while(q--){
int u,v;cin>>u>>v;u--;v--;
int lca=get_lca(u,v);
mentions[u]++;mentions[v]++;
if(lca==u){
queries[lca].pb({u,jump(v,dep[v]-dep[lca]-1)});
}else if(lca==v){
queries[lca].pb({jump(u,dep[u]-dep[lca]-1),v});
}else{
queries[lca].pb({jump(u,dep[u]-dep[lca]-1),jump(v,dep[v]-dep[lca]-1)});
}
}
rec(0,-1);
cout<<ans<<'\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
56660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
152 ms |
168784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1112 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
2652 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
2652 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
131792 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
178 ms |
131780 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
181 ms |
132176 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
181 ms |
132436 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
