제출 #1177258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177258		vnedu	동기화 (JOI13_synchronization)	C++20	30 / 100	38 ms	18504 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 15;
const int M = 2e5 + 25;
const int Q = 1e5 + 15;

int numNode,numState,numQuery,query[Q],state[M];
vector<ii> adj[N];
ii edge[N];
namespace sub1
{
    bool check()
    {
        return (numQuery==1);
    }
    bool cmp(ii x, ii y)
    {
        return x.fi>y.fi;
    }
    int lst[N];
    vector<ii> t[N];
    int dfs(int u, int pa, int time)
    {
//        cout<<u<<' '<<pa<<' '<<time<<'\n';
        int ans=0;
        for (ii p : adj[u])
        {
            int v=p.fi,id=p.se;
            if (v==pa) continue;
            auto it=lower_bound(all(t[id]),make_pair(time,INT_MIN),cmp);
            int cm=INT_MIN;
            if (it!=t[id].end()) maximize(cm,(*it).fi);
            if (it!=t[id].begin())
            {
                --it;
                if (time>=(*it).se) maximize(cm,time);
            }
            if (cm!=INT_MIN) ans+=1+dfs(v,u,cm);
        }
        return ans;
    }
    void solve()
    {
        memset(lst,-1,sizeof(lst));
        for (int tri=1; tri<=numState; ++tri)
        {
            int x=state[tri];
            if (lst[x]==-1) lst[x]=tri;
            else
            {
                t[x].pb(make_pair(tri-1,lst[x]));
                lst[x]=-1;
            }
        }
        for (int i=1; i<numNode; ++i)
        {
            if (lst[i]!=-1) t[i].pb(make_pair(numState,lst[i]));
            reverse(all(t[i]));
        }
//        for (int i=1; i<numNode; ++i)
//        {
//            for (ii cm : t[i]) cout<<cm.fi<<' '<<cm.se<<'\n';
//            cout<<'\n';
//        }
        cout<<dfs(query[1],-1,numState)+1;
    }
}
void solve()
{
    cin>>numNode>>numState>>numQuery;
    for (int i=1; i<numNode; ++i)
    {
        int u,v; cin>>u>>v;
        edge[i]={u,v};
        adj[u].pb({v,i});
        adj[v].pb({u,i});
    }
    for (int i=1; i<=numState; ++i) cin>>state[i];
    for (int i=1; i<=numQuery; ++i) cin>>query[i];
    if (sub1::check()) return void(sub1::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

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