Submission #261840

#	Time	Username	Problem	Language	Result	Execution time	Memory
261840		dantoh000	Colors (RMI18_colors)	C++14	22 / 100	71 ms	7680 KiB

colors

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[150005], b[150005];
vector<int> G[150005];
bool cmp(int x, int y){
    return b[x] > b[y];
}
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 if (m == n-1){
            int star = -1;
            for (int i= 1;i <= n;i++) if(G[i].size() == n-1)star = i;
            assert(star != -1);
            vector<int>  ord(n);
            for (int i=  1; i <= n; i++){
                ord[i-1] = i;
            }
            sort(ord.begin(),ord.end(),cmp);
            for (auto x : ord){
                if (a[x] != b[x]){
                    if (b[x] > a[x]) ans = 0;
                    int found =0;
                    for (int j = 1; j <= n; j++){
                        if (a[j] == b[x] && a[j] <= a[star]){
                            found = 1;
                            break;
                        }
                    }
                    if (!found) ans = 0;
                    a[star] = a[x] = b[x];
                }
            }
            for (int i = 1; i <= n; i++){
                //printf("%d %d\n",a[i],b[i]);
                if (a[i] != b[i]) ans = 0;
            }
        }
        printf("%d\n",ans);
    }
}

Compilation message (stderr)

colors.cpp: In function 'int main()':
colors.cpp:46:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i= 1;i <= n;i++) if(G[i].size() == n-1)star = i;
                                          ~~~~~~~~~~~~^~~~~~
colors.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&tc);
     ~~~~~^~~~~~~~~~
colors.cpp:13: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:16:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i]);
             ~~~~~^~~~~~~~~~~~
colors.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b[i]);
             ~~~~~^~~~~~~~~~~~
colors.cpp:23: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: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22