Menu

Informatics Задача №112694. Дружелюбный интерфейс

February 17, 2017 - informatics.mccme.ru

Language: C++

#include <cstdio>
#include <numeric>
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <queue>
#include <sstream>
#include <deque>

using namespace std;

#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i = 0; i < (n); i++)
#define re return
#define fi first
#define se second
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(abs(x))
#define y0 y3487465
#define y1 y8687969
#define fill(x,y) memset(x,y,sizeof(x))

typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef double D;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<vi> vvi;

template<class T> T abs(T x) { re x > 0 ? x : -x; }

#define filename "j"

int n;
int m;
int ct;
int anc[4000][20];
int tin[4000];
int tout[4000];
vi v[4000];
int s[4000];
vii w;
vi u[4000];
int from[4000];
int q;

int go (int x, int p) {
        tin[x] = ct++;
        anc[x][0] = p;
        for (int i = 0; i < 19; i++)
                anc[x][i + 1] = anc[anc[x][i]][i];
        for (int i = 0; i < sz (v[x]); i++) {
                int y = v[x][i];
                if (y == p) continue;
                go (y, x);
        }
        tout[x] = ct++;
        re 0;
}

int isanc (int a, int b) { re int (tin[a] <= tin[b] && tout[a] >= tout[b]); }

int lca (int a, int b) {
        int j = 19;
        while (!isanc (a, b))
                if (j == 0 || !isanc (anc[a][j], b))
                        a = anc[a][j];
                else
                        j--;
        re a;
}

int check (int a, int b, int d) {
        int c = lca (a, b);
        if (isanc (c, d) && isanc (d, a)) re 1;
        if (isanc (c, d) && isanc (d, b)) re 1;
        re 0;
}

int was[4000];

int go2 (int x) {
        if (was[x] == 1) re 1;
        if (was[x] == 2) re 0;
        was[x] = 1;
        for (int i = 0; i < sz (u[x]); i++)
                if (go2 (u[x][i]))
                        re 1;
        was[x] = 2;
        re 0;
}

int main () {
        scanf ("%d", &n);
        for (int i = 0; i + 1 < n; i++) {
                int a, b;
                scanf ("%d%d", &a, &b); a--; b--;
                v[a].pb (b);
                v[b].pb (a);
        }
        go (0, 0);
        scanf ("%d", &m);
        for (int i = 0; i < m; i++) {
                int x;
                scanf ("%d%d", &s[i], &x); s[i]--; x--;
                from[x] = s[i];
        }
        scanf ("%d", &q);
        for (int i = 0; i < q; i++) {
                int t, x;
                scanf ("%d%d", &t, &x); t--; x--;
                w.pb (mp (x, t));
        }
        m = sz (w);
        for (int i = 0; i < m; i++) {
//                printf ("%d: %d - %d\n", i, from[w[i].fi], w[i].se);
                for (int j = 0; j < m; j++)
                        if (w[i].fi != w[j].fi) {
                                if (check (from[w[i].fi], w[i].se, from[w[j].fi])) {
                                        u[j].pb (i);
//                                        printf ("%d -> %d !\n", j, i);
                                }
                                if (check (from[w[i].fi], w[i].se, w[j].se)) {
                                        u[i].pb (j);
//                                        printf ("%d -> %d ?\n", i, j);
                                }
                        }
        }
        for (int i = 0; i < m; i++)
                if (go2 (i)) {
                        printf ("NO\n");
                        re 0;
                }
        printf ("YES\n");
        return 0;
}

(91)

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on VK

Author of this post : UnknownA AuthorA

Leave a Reply

Your email address will not be published. Required fields are marked *