제출 #963361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963361		MarwenElarbi	Tourism (JOI23_tourism)	C++17	100 / 100	1220 ms	21792 KiB

tourism

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9+7;
const int nax = 1e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct Query{
    int l,r,idx;
};
int n,m;
vi adj[nax];
int c[nax];
vector<Query> queries;
int sz[nax], p[nax], dep[nax];
int segtree[nax*4], id[nax], tp[nax];
int nxt[nax];
int val[nax];
set<int> intervals;
bool cmp(Query x,Query y){
    if(x.r!=y.r) return x.r<y.r;
    else return x.l<y.l;
}
//segtree
void update(int pos,int l,int r,int idx,int value){
    if(l==r){
        segtree[pos]+=value;
        return;
    }
    int mid=(r+l)/2;
    if(idx<=mid) update(pos*2+1,l,mid,idx,value);
    else update(pos*2+2,mid+1,r,idx,value);
    segtree[pos]=segtree[pos*2+1]+segtree[pos*2+2];
    return;
}
int query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return 0;
    if(l>=left&&r<=right) return segtree[pos];
    int mid=(r+l)/2;
    //cout <<l<<" "<<r<<endl;
    return query(pos*2+1,l,mid,left,right)+query(pos*2+2,mid+1,r,left,right);
}
//HLD
int dfs_sz(int cur, int par) {
    sz[cur] = 1;
    p[cur] = par;
    for (int chi : adj[cur]) {
        if (chi == par) continue;
        dep[chi] = dep[cur] + 1;
        p[chi] = cur;
        sz[cur] += dfs_sz(chi, cur);
    }
    return sz[cur];
}

int ct = 1;

void dfs_hld(int cur, int par, int top) {
    id[cur] = ct++;
    tp[cur] = top;
    nxt[cur]=id[top];
    //update(id[cur], v[cur]);
    int h_chi = -1, h_sz = -1;
    for (int chi : adj[cur]) {
        if (chi == par) continue;
        if (sz[chi] > h_sz) {
            h_sz = sz[chi];
            h_chi = chi;
        }
    }
    if (h_chi == -1) return;
    dfs_hld(h_chi, cur, top);
    for (int chi : adj[cur]) {
        if (chi == par || chi == h_chi) continue;
        dfs_hld(chi, cur, chi);
    }
}
void updateAns(int l, int r, int x) {
    //cout <<l<<" "<<r<<" "<<x<<endl;
    set<int>::iterator it;
    it = intervals.lower_bound(l);
    if (it != intervals.begin()) it--;
    vector<int> to_rem;
    vector<int> to_add;
    while (it != intervals.end()) {
        int a = *it;
        int b = nxt[a];
        if (a > r) break;
        if (a < l && b < l) {
            it++;
            continue;
        }
        if (a < l) {
            update(0,0,m+2,val[a], -(b - a + 1));
            nxt[a] = l - 1;
            update(0,0,m+2,val[a], (nxt[a] - a + 1));
        } else {
            update(0,0,m+2,val[a], -(b - a + 1));
            to_rem.pb(a);
        }
        if (b > r) {
            to_add.pb(r + 1);
            val[r+1]=val[a];
            update(0,0,m+2,val[a], b - r);
            nxt[r + 1] = b;
        }
        it++;
    }
    //cout <<segtree[0]<<endl;
    nxt[l] = r;
    val[l] = x;
    update(0,0,m+2,x, r - l + 1);
    //cout <<segtree[0]<<endl;
    for (auto &u : to_rem) {
        assert(intervals.count(u));
        intervals.erase(u);
    }
    for (auto &u : to_add) {
        intervals.insert(u);
    }
    intervals.insert(l);
}
void path(int x, int y,int value) {
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
        updateAns(id[tp[x]], id[x], value);
        x = p[tp[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    updateAns(id[x], id[y], value);
    return;
}

int main(){
    optimise;
    //setIO("dec");
    int q;
    cin>>n>>m>>q;
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for (int i = 0; i < m; ++i)
    {
        cin>>c[i];
        c[i]--;
    }
    dfs_sz(0,-1);
    dfs_hld(0,-1,0);
    for (int i = 0; i < q; ++i)
    {
        queries.emplace_back();
        cin>>queries[i].l>>queries[i].r;
        queries[i].idx=i;
        queries[i].l--;
        queries[i].r--;
    }
    //return 0;
    //cout <<"nabba"<<endl;
    sort(queries.begin(),queries.end(),cmp);
    int j=0;
    int ans[q];
    for (int i = 0; i < m; ++i)
    {
        //cout <<queries[j].l<<" "<<queries[j].r<<" "<<queries[j].idx<<endl;
        if(i){
            path(c[i-1],c[i],i);
            //cout <<"nab"<<endl;
        }path(c[i],c[i],i+1);
        while(j<q&&queries[j].r==i){
            ans[queries[j].idx]=query(0,0,m+2,queries[j].l+1,m+1);
            //cout <<"kalil"<<endl;
            j++;
        }
        
    }
    for (int i = 0; i < q; ++i)
    {
        cout <<ans[i]<<endl;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp: In function 'void setIO(std::string)':
tourism.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41