Submission #261847

#	Time	Username	Problem	Language	Result	Execution time	Memory
261847		dantoh000	Colors (RMI18_colors)	C++14	47 / 100	3072 ms	7032 KiB

colors

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[150005], b[150005];
vector<int> G[150005];
int vis[100005];
bool cmp(int x, int y){
    return a[x] > a[y];
}
void dfs(int u){
    for (auto v : G[u]){
        if (a[v] < a[u]) continue;
        if (b[v] > a[u]) continue;
        if (vis[v]) continue;
        vis[v] = 1;
        a[v] = a[u];
        dfs(v);
    }
}
int main(){
    int tc;
    scanf("%d",&tc);
    while (tc--){
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; i++){
            G[i].clear();
            scanf("%d",&a[i]);
        }
        for (int i = 1; i <= n; i++){
            scanf("%d",&b[i]);
        }
        for (int i = 1; i <= m; i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int ans=1;
        if (m == n*(n-1)/2){
            for (int i = 1; i <= n; i++){
                if (a[i] != b[i]){
                    if (b[i] > a[i]){
                        ans =0;
                    }
                    else{
                        int found = 0;
                        for (int j = 1; j <= n; j++){
                            if (a[j] == b[i]) found = 1;
                        }
                        if (!found) ans = 0;
                    }
                }
            }
        }
        else{
            vector<int> ord(n);
            for (int i =1 ; i <= n; i++){
                ord[i-1] = i;
            }
            sort(ord.begin(),ord.end(),cmp);
            for (auto u : ord){
                for (int i = 1; i <= n; i++){
                    vis[i] = 0;
                }
                dfs(u);
            }
            for (int i =1 ; i <= n; i++){
                if (a[i] != b[i]){
                    ans = 0;
                }
            }
        }
        printf("%d\n",ans);
    }
}

Compilation message (stderr)

colors.cpp: In function 'int main()':
colors.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&tc);
     ~~~~~^~~~~~~~~~
colors.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&n,&m);
         ~~~~~^~~~~~~~~~~~~~
colors.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i]);
             ~~~~~^~~~~~~~~~~~
colors.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b[i]);
             ~~~~~^~~~~~~~~~~~
colors.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 0 / 15
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 10 / 10
• Subtask 8: 0 / 22