Submission #154537

#	Time	Username	Problem	Language	Result	Execution time	Memory
154537		phillip	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	853 ms	8720 KiB

usmjeri

#include <bits/stdc++.h>
#define lp (pos+pos+1)
#define rp (2*pos+2)
#define m (l+r)/2
using namespace std;
int pt;
int rep[500009],sz[500009],mod=1e9+7;
int find(int x)
{
    if(x==-1)return -1;
    while(x!=rep[x])x=rep[x];
    return x;
}
void cn(int x,int y)
{
    if(min(x,y)==-1)return;
    x=find(x);y=find(y);
    if(x==y)return;
    if(sz[x]<sz[y])swap(x,y);
    sz[x]+=sz[y];
    rep[y]=x;
}
int seg[1200009],a[300009];
void laz(int pos,int l,int r)
{
    if(seg[pos]==-1)return;
    seg[pos]=find(seg[pos]);
    if(l==r)
    {
        cn(seg[pos],a[l]);
        a[l]=find(seg[pos]);
        seg[pos]=-1;
        return;
    }
    cn(seg[pos],seg[lp]);
    cn(seg[pos],seg[rp]);
    seg[pos]=find(seg[pos]);
    seg[lp]=seg[pos];
    seg[rp]=seg[pos];
    seg[pos]=-1;
}
void upd(int pos,int l,int r,int b,int e,int o)
{
    laz(pos,l,r);
    if(b<=l&&r<=e)
    {
        seg[pos]=o;
        laz(pos,l,r);
        return;
    }
    if(m>=b)upd(lp,l,m,b,e,o);
    if(m<e)upd(rp,m+1,r,b,e,o);
}
void frsh(int pos,int l,int r)
{
    laz(pos,l,r);
    if(l==r)return;
    frsh(lp,l,m);
    frsh(rp,m+1,r);
}
int n,q,x,y;
int vis[300009];
int main()
{
    memset(a,-1,sizeof(a));
    memset(seg,-1,sizeof(seg));
    cin>>n>>q;
    for(int i=0;i<q;i++)
    {
        sz[i]=1;
        rep[i]=i;
    }
    for(int i=0;i<n-1;i++)cin>>x>>x;
    for(int i=0;i<q;i++)
    {
        cin>>x>>y;
        x--;y-=2;
        upd(0,0,n-2,x,y,i);
    }
    frsh(0,0,n-2);
    int ans=1;
    for(int i=0;i<n-1;i++)
    {
        ans%=mod;
        if(a[i]==-1)ans*=2;
        else
        {
            a[i]=find(a[i]);
            if(vis[a[i]])continue;
            vis[a[i]]=1;
            ans*=2;
        }
    }
    cout<<ans%mod;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14