oj.uz

답안 #225408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225408 2020-04-20T13:56:28 Z nicolaalexandra Colors (RMI18_colors) C++14
62 / 100
 3000 ms 63224 KB 
#include <bits/stdc++.h>
#define DIM 300010
#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=20;i>=0;i--){
        if (dp[x][i].nod && 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=20;i>=0;i--){
        if (dp[y][i].nod && 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 = max (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[b[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 183 ms 37112 KB Output is correct
2 Correct 77 ms 36216 KB Output is correct
3 Correct 32 ms 35704 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 392 ms 38344 KB Output is correct
2 Correct 101 ms 37368 KB Output is correct
3 Correct 32 ms 36992 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 392 ms 38344 KB Output is correct
2 Correct 101 ms 37368 KB Output is correct
3 Correct 32 ms 36992 KB Output is correct
4 Correct 603 ms 39928 KB Output is correct
5 Correct 584 ms 49020 KB Output is correct
6 Correct 726 ms 63224 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 37112 KB Output is correct
2 Correct 77 ms 36216 KB Output is correct
3 Correct 32 ms 35704 KB Output is correct
4 Correct 392 ms 38344 KB Output is correct
5 Correct 101 ms 37368 KB Output is correct
6 Correct 32 ms 36992 KB Output is correct
7 Correct 2520 ms 38396 KB Output is correct
8 Correct 910 ms 37368 KB Output is correct
9 Correct 214 ms 36864 KB Output is correct

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3073 ms 39396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 453 ms 37624 KB Output is correct
2 Correct 156 ms 37112 KB Output is correct
3 Correct 188 ms 36960 KB Output is correct

Subtask #8
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 37112 KB Output is correct
2 Correct 77 ms 36216 KB Output is correct
3 Correct 32 ms 35704 KB Output is correct
4 Correct 184 ms 37244 KB Output is correct
5 Correct 392 ms 38344 KB Output is correct
6 Correct 101 ms 37368 KB Output is correct
7 Correct 32 ms 36992 KB Output is correct
8 Correct 603 ms 39928 KB Output is correct
9 Correct 584 ms 49020 KB Output is correct
10 Correct 726 ms 63224 KB Output is correct
11 Correct 2520 ms 38396 KB Output is correct
12 Correct 910 ms 37368 KB Output is correct
13 Correct 214 ms 36864 KB Output is correct
14 Execution timed out 3073 ms 39396 KB Time limit exceeded
15 Halted 0 ms 0 KB -