Submission #885355

#	Time	Username	Problem	Language	Result	Execution time	Memory
885355		cpptowin	Birthday gift (IZhO18_treearray)	C++17	100 / 100	903 ms	202228 KiB

treearray

#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
vi ke[maxn];
set<int> s1[maxn],s2[maxn];
int n,m,a[maxn],q;
int h[maxn],par[maxn][20];
void dfs(int u,int parent)
{
    for(int v : ke[u])
    {
        if(v == parent) continue;
        h[v] = h[u] + 1;
        par[v][0] = u;
        dfs(v,u);
    }
}
int lca(int u,int v)
{
    if(h[u] < h[v]) swap(u,v);
    int del = h[u] - h[v];
    fod(i,19,0) if(bit(del,i)) u = par[u][i];
    if(u == v) return u;
    fod(i,19,0) if(par[u][i] != par[v][i])
    {
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m >> q;
    fo(i,1,n - 1)
    {
        int u,v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    dfs(1,1);
    fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
    fo(i,1,m)
    {
        cin >> a[i];
        s1[a[i]].insert(i);
    }
    fo(i,1,m - 1)
    {
        s2[lca(a[i],a[i + 1])].insert(i);
    }
    while(q--)
    {
        int type;
        cin >> type;
        if(type == 1)
        {
            int pos,v;
            cin >> pos >> v;
            auto lb = s1[a[pos]].lower_bound(pos);
            s1[a[pos]].erase(lb);
            s1[v].insert(pos);
            if(pos > 1)
            {
                int _lca = lca(a[pos],a[pos - 1]);
                lb = s2[_lca].lower_bound(pos - 1);
                s2[_lca].erase(lb);
                _lca = lca(v,a[pos - 1]);
                s2[_lca].insert(pos - 1);
            }
            if(pos < m)
            {
                int _lca = lca(a[pos],a[pos + 1]);
                lb = s2[_lca].lower_bound(pos);
                s2[_lca].erase(lb);
                _lca = lca(v,a[pos + 1]);
                s2[_lca].insert(pos);
            }
            a[pos] = v;
        }
        else 
        {
            int l,r,v;
            cin >> l >> r >> v;
            auto lb = s1[v].lower_bound(l);
            if(lb != s1[v].end() and *lb >= l and *lb <= r) cout << *lb << ' ' << *lb << "\n";
            else 
            {
                lb = s2[v].lower_bound(l);
                if(*lb >= l and *lb < r) cout << *lb << ' ' << *lb + 1 << "\n";
                else cout << -1 << ' ' << -1 << "\n";
            }
        }
    }
}

Compilation message (stderr)

treearray.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
treearray.cpp: In function 'int main()':
treearray.cpp:54:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:55:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44