oj.uz

Submission #261840

# Submission time Handle Problem Language Result Execution time Memory
261840 2020-08-12T06:10:47 Z dantoh000 Colors (RMI18_colors) C++14
22 / 100
 71 ms 7680 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3840 KB Output is correct
2 Correct 26 ms 3968 KB Output is correct
3 Correct 5 ms 3968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3840 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3840 KB Output is correct
2 Correct 26 ms 3968 KB Output is correct
3 Correct 5 ms 3968 KB Output is correct
4 Runtime error 9 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 7680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3840 KB Output is correct
2 Correct 26 ms 3968 KB Output is correct
3 Correct 5 ms 3968 KB Output is correct
4 Correct 69 ms 3840 KB Output is correct
5 Runtime error 9 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -