Submission #1261368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261368		4o2a	Synchronization (JOI13_synchronization)	C++20	30 / 100	211 ms	33388 KiB

synchronization

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "what"
using namespace std;
typedef long long ll;

constexpr int N = 2e5 + 1;
int n, m, q, t[N], res = 1;
map<pair<int, int>, int> mp;
vector<int> T[N], adj[N];
pair<int, int> E[N];

void dfs(int u, int p)
{
    if (p == -1)
        t[u] = m+1;
    else
    {
        pair<int, int> e = {u, p};
        if (e.fi > e.se)
            swap(e.fi, e.se);
        int i = mp[e];
        auto it = upper_bound(T[i].begin(), T[i].end(), t[p]);
        if (it == T[i].begin())
            t[u] = 0;
        else
        {
            int l = prev(it) - T[i].begin();
            t[u] = (l&1 ? T[i][l] : t[p]);
        }
    }
    for (int v: adj[u])
        if (v != p)
        {
            pair<int, int> e = {u, v};
            if (e.fi > e.se)
                swap(e.fi, e.se);
            int i = mp[e];
            res += (!T[i].empty() && T[i][0] <= t[u]);
            dfs(v, u);
        }
}

void solve()
{
    cin>>n>>m>>q;
    assert(q == 1);
    for (int i = 1; i < n; ++i)
    {
        int u, v; cin>>u>>v;
        if (u > v)
            swap(u, v);
        E[i] = {u, v};
        mp[E[i]] = i;
        adj[u].pb(v), adj[v].pb(u);
    }
    for (int i = 1; i <= m; ++i)
    {
        int d; cin>>d;
        T[d].pb(i);
    }
    for (int i = 1; i < n; ++i)
        if (T[i].size()%2 == 1)
            T[i].pb(m+1);
    int u; cin>>u;
    dfs(u, -1);
    cout<<res;
}

int main()
{
    if (fopen(_F".INP", "r"))
    {
        freopen(_F".INP", "r", stdin);
        freopen(_F".OUT", "w", stdout);
    }
    else if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        //freopen("test.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int Test = 1; //cin>>Test;
    while (Test--) solve();
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(_F".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(_F".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40