oj.uz

답안 #225402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225402 2020-04-20T13:44:03 Z nicolaalexandra Colors (RMI18_colors) C++14
62 / 100
 2732 ms 57976 KB 
#include <bits/stdc++.h>
#define DIM 150010
#define INF 2000000000
using namespace std;
vector <int> L[DIM],poz[DIM*4];
int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM],v[DIM],viz[DIM],E[DIM*4],first[DIM],level[DIM],p[DIM*4],idx[DIM];
int t,n,m,i,j,x,y,k,sol,mini,maxi,ok,g;
struct seg_tree{
    int minia,maxib;
} aint[4*DIM];
struct idk{
    int nod, minia, maxib;
} dp[DIM][30];
pair <int,int> rmq[30][DIM*4];

void dfs (int nod){
    viz[nod] = 1;
    v[++k] = nod;
    for (auto vecin : L[nod])
        if (!viz[vecin])
            dfs (vecin);
}
void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].minia = a[v[st]];
        aint[nod].maxib = b[v[st]];
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod].minia = min (aint[nod<<1].minia,aint[(nod<<1)|1].minia);
    aint[nod].maxib = max (aint[nod<<1].maxib,aint[(nod<<1)|1].maxib);
}
void query (int nod, int st, int dr, int x, int y){

    if (x <= st && dr <= y){
        mini = min (mini,aint[nod].minia);
        maxi = max (maxi,aint[nod].maxib);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query(nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}
int solve (int v[], int k){
    for (i=1;i<=4*k;i++){
        poz[i].clear();
        aint[i] = {0,0};
    }

    for (i=1;i<=k;i++)
        poz[a[v[i]]].push_back(i);


    build (1,1,k);

    int ok = 1;

    for (i=1;i<=k;i++){
        if (a[v[i]] == b[v[i]])
            continue;

        int lft = 0, rgh = 0;
        for (auto it : poz[b[v[i]]]){
            if (it < i)
                lft = it;
            if (it > i){
                rgh = it;
                break;
            }
        }

        int ok2 = 0;
        if (lft){
            mini = INF, maxi = -INF;
            query (1,1,k,lft,i-1);
            if (mini >= b[v[i]] && maxi <= b[v[i]])
                ok2 = 1;
        }
        if (rgh){
            mini = INF, maxi = -INF;
            query (1,1,k,i+1,rgh);
            if (mini >= b[v[i]] && maxi <= b[v[i]])
                ok2 = 1;
        }

        if (!ok2){
            ok = 0;
            break;
        }
    }

    return ok;
}

void dfs2 (int nod){
    viz[nod] = 1;
    if (nod != i && a[nod] == b[i])
        g = 1;
    for (auto vecin : L[nod])
        if (!viz[vecin])
            if (a[vecin] >= b[i] && b[vecin] <= b[i])
                dfs2 (vecin);
}

void dfs3 (int nod, int tata){
    dp[nod][0] = {tata, a[nod],b[nod]};
    E[++k] = nod;
    first[nod] = k;
    level[nod] = 1 + level[tata];
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs3 (vecin,nod);
            E[++k] = nod;
        }
}

int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy - posx + 1];
    pair <int, int> sol = min (rmq[nr][posx], rmq[nr][posy - (1<<nr) + 1]);
    return E[sol.second];
}

void solve2 (int x, int y){

    int lca = get_lca (x,y);
    for (int i=30;i>0;i--){
        if (level[dp[x][i].nod] >= level[lca]){
            mini = min (mini,dp[x][i].minia);
            maxi = max (maxi,dp[x][i].maxib);
            x = dp[x][i].nod;
        }
    }

    for (int i=30;i>0;i--){
        if (level[dp[y][i].nod] >= level[lca]){
            mini = min (mini,dp[y][i].minia);
            maxi = max (maxi,dp[y][i].maxib);
            x = dp[y][i].nod;
        }
    }

}

int main (){

  //  ifstream cin ("colors2.in");
  //  ofstream cout ("colors2.out");

    cin>>t;
    for (int q=1;q<=t;q++){
        if (q == 36)
            q = 36;
        cin>>n>>m;

        for (i=1;i<=n;i++){
            L[i].clear();
            f[i] = 0;
        }

        for (i=1;i<=n;i++){
            cin>>a[i];
            f[a[i]]++;
        }

        int ok = 1;
        for (i=1;i<=n;i++){
            cin>>b[i];
            if (b[i] > a[i] || !f[b[i]])
                ok = 0;
        }
        for (i=1;i<=m;i++){
            cin>>x>>y;
            L[x].push_back(y);
            L[y].push_back(x);
        }

        if (!ok){
            cout<<0<<"\n";
            continue;
        }

        if (n == 1 && !m){
            if (a[1] == b[1])
                cout<<"1\n";
            else cout<<"0\n";
            continue;
        }

        if (n == 2 && m == 1){
            if ( (a[1] == b[1] && a[2] == b[2]) || (min (a[1],a[2]) == b[1] && min (a[1],a[2]) == b[2]) )
                cout<<"1\n";
            else cout<<"0\n";
            continue;
        }

        /// graf stea
        int nod = 0, cnt = 0;
        for (i=1;i<=n;i++){
            if (L[i].size() == 1)
                cnt++;
            else nod = i;
        }
        if (cnt == n-1){

            int maxi = 0, mini = n+1;
            for (i=1;i<=n;i++){
                if (b[i] == a[i])
                    continue;

                maxi = max (maxi,b[i]);
                if (i != nod)
                    mini = min (mini,b[i]);
            }
            if (maxi && (maxi > a[nod] || mini < b[nod])){
                cout<<"0\n";
                continue;
            }
            /// acum sa vad daca exista b[nod]
            int ok = 0;
            if (!maxi)
                ok = 1;
            for (i=1;i<=n;i++)
                if (i != nod && b[i] == b[nod]){
                    ok = 1;
                    break;
                }
            cout<<ok<<"\n";

            continue;
        }

        /// graf complet
        if (m == 1LL*n*(n-1)/2){

            cout<<1<<"\n";
            continue;
        }

        /// lant
        int start = 0;
        cnt = 0;
        for (i=1;i<=n;i++)
            if (L[i].size() == 1){
                if (!start)
                    start = i;
                cnt++;
            }

        if (cnt == 2 && m == n-1){
            memset (viz,0,sizeof viz); k = 0;
            dfs (start);

            if (solve (v,k))
                cout<<"1\n";
            else cout<<"0\n";

            continue;
        }

        /// arbore

        if (1LL*n*n <= 5000000){
            for (i=1;i<=n;i++){
                if (a[i] == b[i])
                    continue;
                memset (viz,0,sizeof viz);
                g = 0;
                dfs2 (i);
                if (!g)
                    break;
            }
            if (i > n)
                cout<<"1\n";
            else cout<<"0\n";

            continue;
        }

        /// permutarea
        k = 0;
        dfs3 (1,0);

        for (i=1;i<=k;i++)
            rmq[0][i] = make_pair(level[E[i]],i);

        for (i=1;(1<<i)<=k;i++)
            for (j=1;j<=k;j++){
                rmq[i][j] = rmq[i-1][j];
                if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                    rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
            }

        for (i=2;i<=k;i++)
            p[i] = p[i/2] + 1;


        for (j=1;(1<<j)<=n;j++)
            for (i=1;i<=n;i++){
                dp[i][j].nod = dp[dp[i][j-1].nod][j-1].nod;
                dp[i][j].minia = min (dp[i][j-1].minia, dp[ dp[i][j-1].nod ][j-1].minia);
                dp[i][j].maxib = min (dp[i][j-1].maxib, dp[ dp[i][j-1].nod ][j-1].maxib);
            }

        for (i=1;i<=n;i++)
            idx[a[i]] = i;

        for (i=1;i<=n;i++){
            if (a[i] == b[i])
                continue;

            mini = INF, maxi = -INF;
            solve2 (idx[a[i]],i);

            if (mini < b[i] || maxi > b[i])
                break;

        }
        if (i > n)
            cout<<"1\n";
        else cout<<"0\n";

    }

    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 17920 KB Output is correct
2 Correct 66 ms 18048 KB Output is correct
3 Correct 18 ms 18048 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 17920 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 18620 KB Output is correct
2 Correct 78 ms 18560 KB Output is correct
3 Correct 21 ms 18688 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 18620 KB Output is correct
2 Correct 78 ms 18560 KB Output is correct
3 Correct 21 ms 18688 KB Output is correct
4 Correct 477 ms 18560 KB Output is correct
5 Correct 564 ms 25592 KB Output is correct
6 Correct 733 ms 39672 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 17920 KB Output is correct
2 Correct 66 ms 18048 KB Output is correct
3 Correct 18 ms 18048 KB Output is correct
4 Correct 273 ms 18620 KB Output is correct
5 Correct 78 ms 18560 KB Output is correct
6 Correct 21 ms 18688 KB Output is correct
7 Correct 1349 ms 18688 KB Output is correct
8 Correct 509 ms 18680 KB Output is correct
9 Correct 138 ms 18560 KB Output is correct

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2732 ms 18808 KB Output is correct
2 Incorrect 563 ms 57976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 18560 KB Output is correct
2 Correct 99 ms 18560 KB Output is correct
3 Correct 129 ms 18680 KB Output is correct

Subtask #8
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 17920 KB Output is correct
2 Correct 66 ms 18048 KB Output is correct
3 Correct 18 ms 18048 KB Output is correct
4 Correct 169 ms 17920 KB Output is correct
5 Correct 273 ms 18620 KB Output is correct
6 Correct 78 ms 18560 KB Output is correct
7 Correct 21 ms 18688 KB Output is correct
8 Correct 477 ms 18560 KB Output is correct
9 Correct 564 ms 25592 KB Output is correct
10 Correct 733 ms 39672 KB Output is correct
11 Correct 1349 ms 18688 KB Output is correct
12 Correct 509 ms 18680 KB Output is correct
13 Correct 138 ms 18560 KB Output is correct
14 Correct 2732 ms 18808 KB Output is correct
15 Incorrect 563 ms 57976 KB Output isn't correct
16 Halted 0 ms 0 KB -