oj.uz

Submission #1085205

# Submission time Handle Problem Language Result Execution time Memory
1085205 2024-09-07T16:56:02 Z TlenekWodoru Werewolf (IOI18_werewolf) C++17
15 / 100
 759 ms 524288 KB 
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct ZAP
{
    int v,ind;
};
vector<int>D[200009];
vector<int>S[2009];
bool Nawiazanie[2009];
vector<ZAP>Q1[200009],Q2[200009];
int spojna[200009];
vector<int>V[200009],V2[200009];
int JakieS[200009];
vector<int>Z1[200009],Z2[200009];
int Z1s[200009],Z2s[200009];
bool CzyNachodzi[2009][2009];
bool help[200009];
int n,m,q,SQRT,h=0;
void Polacz(int a, int b)
{
    a=spojna[a];
    b=spojna[b];
    if(a==b){return;}
    if(V2[a].size()<V2[b].size()){swap(a,b);}
    for(int u : V[b])
    {
        V[a].push_back(u);
    }
    for(int u : V2[b])
    {
        spojna[u]=a;
        V2[a].push_back(u);
    }
    V2[b].clear();
    vector<int>Pier;
    if(JakieS[a]!=-1){Pier.push_back(JakieS[a]);}
    if(JakieS[b]!=-1){Pier.push_back(JakieS[b]);}
    if((int)V[a].size()>=SQRT)
    {
        h++;
        for(int i=1;i<=SQRT;i++)
        {
            S[h].push_back(V[a].back());
            V[a].pop_back();
        }
        Pier.push_back(h);
    }
    while((int)Pier.size()>1)
    {
        const int aa=Pier[Pier.size()-2];
        const int bb=Pier[Pier.size()-1];
        Pier.pop_back();
        Pier.pop_back();
        h++;
        Pier.push_back(h);
        Nawiazanie[h]=1;
        S[h]={aa,bb};
    }
    if((int)Pier.size()==0){JakieS[a]=-1;}
    else{JakieS[a]=Pier[0];}
}
void Polacz2(int a, int b)
{
    a=spojna[a];
    b=spojna[b];
    if(a==b){return;}
    if(V[a].size()<V[b].size()){swap(a,b);}
    for(int u : V[b])
    {
        spojna[u]=a;
        V[a].push_back(u);
    }
    V[b].clear();
}
vector<int>check_validity(int N, vector<int>E1, vector<int>E2, vector<int>AA, vector<int>BB, vector<int>LL, vector<int>RR)
{
    n=N;
    m=E1.size();
    q=AA.size();
    vector<int>ODP(q);
    SQRT=max(2,(int)sqrt(n));
    SQRT=INT_MAX;
    for(int i=0;i<m;i++)
    {
        const int a=E1[i],b=E2[i];
        D[a].push_back(b);
        D[b].push_back(a);
    }
    for(int i=0;i<q;i++)
    {
        Q1[RR[i]].push_back({BB[i],i});
        Q2[LL[i]].push_back({AA[i],i});
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};V2[i]={i};}
    for(int i=0;i<n;i++)
    {
        for(int som : D[i])
        {
            if(som<=i)
            Polacz(i,som);
        }
        for(auto[v,ind] : Q1[i])
        {
            Z1[ind]=V[spojna[v]];
            Z1s[ind]=JakieS[spojna[v]];
        }
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};V2[i]={i};}
    for(int i=n-1;i>=0;i--)
    {
        for(int som : D[i])
        {
            if(som>=i)
            Polacz(i,som);
        }
        for(auto[v,ind] : Q2[i])
        {
            Z2[ind]=V[spojna[v]];
            Z2s[ind]=JakieS[spojna[v]];
        }
    }
    for(int i=1;i<=h;i++)
    {
        CzyNachodzi[i][i]=1;
        if(Nawiazanie[i]){continue;}
        for(int j=i+1;j<=h;j++)
        {
            if(Nawiazanie[j]){continue;}
            for(int u : S[i])
            {
                help[u]=1;
            }
            bool cv=0;
            for(int u : S[j])
            {
                if(help[u])
                {
                    cv=1;
                    break;
                }
            }
            CzyNachodzi[i][j]=cv;
            CzyNachodzi[j][i]=cv;
        }
    }
    /**for(int i=1;i<=h;i++)
    {
        if(Nawiazanie[i])
        {
            cout<<"i="<<i<<" a="<<S[i][0]<<" b="<<S[i][1]<<endl;
        }
        else
        {
            cout<<"i="<<i<<"| ";
            for(int u : S[i])
            {
                cout<<u<<",";
            }
            cout<<endl;
        }
    }**/
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<i;j++)
        {
            bool cv;
            if(Nawiazanie[i]==0&&Nawiazanie[j]==0){continue;}
            if(Nawiazanie[j]==0)
            {
                cv=(CzyNachodzi[j][S[i][0]]|CzyNachodzi[j][S[i][1]]);
            }
            else if(Nawiazanie[i]==0)
            {
                cv=(CzyNachodzi[i][S[j][0]]|CzyNachodzi[i][S[j][1]]);
            }
            else
            {
                cv=(CzyNachodzi[S[i][0]][S[j][0]]|CzyNachodzi[S[i][0]][S[j][1]]|
                    CzyNachodzi[S[i][1]][S[j][0]]|CzyNachodzi[S[i][1]][S[j][1]]);
            }
            CzyNachodzi[i][j]=cv;
            CzyNachodzi[j][i]=cv;
        }
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};}
    for(int i=0;i<n;i++)
    {
        for(int som : D[i])
        {
            if(som<=i)
            Polacz2(i,som);
        }
        for(auto[v,ind] : Q1[i])
        {
            int s=spojna[v];
            for(int u : Z2[ind])
            {
                if(spojna[u]==s)
                {
                    ODP[ind]=1;
                    break;
                }
            }
        }
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};}
    for(int i=n-1;i>=0;i--)
    {
        for(int som : D[i])
        {
            if(som>=i)
            Polacz2(i,som);
        }
        for(auto[v,ind] : Q2[i])
        {
            int s=spojna[v];
            for(int u : Z1[ind])
            {
                if(spojna[u]==s)
                {
                    ODP[ind]=1;
                    break;
                }
            }
        }
    }
    for(int i=0;i<q;i++)
    {
        if(Z1s[i]==-1||Z2s[i]==-1){continue;}
        if(CzyNachodzi[Z1s[i]][Z2s[i]])
        {
            ODP[i]=1;
        }
    }
    for(int i=0;i<q;i++)
    {
        if(AA[i]<LL[i]||RR[i]<BB[i]){ODP[i]=0;}
    }
    return ODP;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34140 KB Output is correct
2 Correct 13 ms 34140 KB Output is correct
3 Correct 13 ms 34140 KB Output is correct
4 Correct 19 ms 34140 KB Output is correct
5 Correct 14 ms 34140 KB Output is correct
6 Correct 13 ms 34248 KB Output is correct
7 Correct 20 ms 34252 KB Output is correct
8 Correct 14 ms 34140 KB Output is correct
9 Correct 21 ms 34140 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34140 KB Output is correct
2 Correct 13 ms 34140 KB Output is correct
3 Correct 13 ms 34140 KB Output is correct
4 Correct 19 ms 34140 KB Output is correct
5 Correct 14 ms 34140 KB Output is correct
6 Correct 13 ms 34248 KB Output is correct
7 Correct 20 ms 34252 KB Output is correct
8 Correct 14 ms 34140 KB Output is correct
9 Correct 21 ms 34140 KB Output is correct
10 Correct 30 ms 67156 KB Output is correct
11 Correct 41 ms 58216 KB Output is correct
12 Correct 18 ms 36444 KB Output is correct
13 Correct 30 ms 69712 KB Output is correct
14 Correct 31 ms 62468 KB Output is correct
15 Correct 31 ms 57424 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 333252 KB Output is correct
2 Runtime error 345 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34140 KB Output is correct
2 Correct 13 ms 34140 KB Output is correct
3 Correct 13 ms 34140 KB Output is correct
4 Correct 19 ms 34140 KB Output is correct
5 Correct 14 ms 34140 KB Output is correct
6 Correct 13 ms 34248 KB Output is correct
7 Correct 20 ms 34252 KB Output is correct
8 Correct 14 ms 34140 KB Output is correct
9 Correct 21 ms 34140 KB Output is correct
10 Correct 30 ms 67156 KB Output is correct
11 Correct 41 ms 58216 KB Output is correct
12 Correct 18 ms 36444 KB Output is correct
13 Correct 30 ms 69712 KB Output is correct
14 Correct 31 ms 62468 KB Output is correct
15 Correct 31 ms 57424 KB Output is correct
16 Correct 759 ms 333252 KB Output is correct
17 Runtime error 345 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -