Submission #602607

#	Time	Username	Problem	Language	Result	Execution time	Memory
602607		SamAnd	Jail (JOI22_jail)	C++17	0 / 100	28 ms	1972 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 255;

int n;
vector<int> g[N];

int m;
int s[N], t[N];

bool dfs(int x, int p, int y, vector<int>& v)
{
    v.push_back(x);
    if (x == y)
        return true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        if (dfs(h, x, y, v))
            return true;
    }
    v.pop_back();
    return false;
}

vector<int> gg[N][N];
int c[N];
bool dfs1(int s, int x)
{
    c[x] = 1;
    for (int i = 0; i < gg[s][x].size(); ++i)
    {
        int h = gg[s][x][i];
        if (c[h] == 1)
            return true;
        if (c[h] == 0)
        {
            if (dfs1(s, h))
                return true;
        }
    }
    c[x] = 2;
    return false;
}

void solv()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        g[i].clear();
        for (int j = 1; j <= n; ++j)
            gg[i][j].clear();
    }

    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    cin >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> s[i] >> t[i];
    }

    bool ans = true;
    for (int i = 1; i <= m; ++i)
    {
        vector<int> v;
        assert(dfs(s[i], s[i], t[i], v));
        v.push_back(t[i]);
        reverse(all(v));
        v.push_back(s[i]);
        reverse(all(v));
        for (int i = 1; i < sz(v) - 1; ++i)
        {
            gg[v[i]][v[i - 1]].push_back(v[i + 1]);
        }
    }

    for (int s = 1; s <= n; ++s)
    {
        for (int i = 1; i <= n; ++i)
            c[i] = 0;
        for (int x = 1; x <= n; ++x)
        {
            if (c[x])
                continue;
            if (dfs1(s, x))
            {
                cout << "No\n";
                return;
            }
        }
    }
    cout << "Yes\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'bool dfs(int, int, int, std::vector<int>&)':
jail.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
jail.cpp: In function 'bool dfs1(int, int)':
jail.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < gg[s][x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~
jail.cpp: In function 'void solv()':
jail.cpp:80:10: warning: unused variable 'ans' [-Wunused-variable]
   80 |     bool ans = true;
      |          ^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23