oj.uz

Submission #261847

# Submission time Handle Problem Language Result Execution time Memory
261847 2020-08-12T06:32:38 Z dantoh000 Colors (RMI18_colors) C++14
47 / 100
 3000 ms 7032 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3840 KB Output is correct
2 Correct 50 ms 3956 KB Output is correct
3 Correct 23 ms 3968 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3840 KB Output is correct
2 Correct 34 ms 4160 KB Output is correct
3 Correct 9 ms 3968 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3840 KB Output is correct
2 Correct 34 ms 4160 KB Output is correct
3 Correct 9 ms 3968 KB Output is correct
4 Correct 180 ms 4856 KB Output is correct
5 Execution timed out 3069 ms 7032 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3840 KB Output is correct
2 Correct 50 ms 3956 KB Output is correct
3 Correct 23 ms 3968 KB Output is correct
4 Correct 88 ms 3840 KB Output is correct
5 Correct 34 ms 4160 KB Output is correct
6 Correct 9 ms 3968 KB Output is correct
7 Correct 98 ms 4472 KB Output is correct
8 Correct 44 ms 4224 KB Output is correct
9 Correct 18 ms 3968 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 3960 KB Output is correct
2 Execution timed out 3072 ms 5880 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3840 KB Output is correct
2 Correct 36 ms 4224 KB Output is correct
3 Correct 38 ms 3968 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3840 KB Output is correct
2 Correct 50 ms 3956 KB Output is correct
3 Correct 23 ms 3968 KB Output is correct
4 Correct 85 ms 3840 KB Output is correct
5 Correct 88 ms 3840 KB Output is correct
6 Correct 34 ms 4160 KB Output is correct
7 Correct 9 ms 3968 KB Output is correct
8 Correct 180 ms 4856 KB Output is correct
9 Execution timed out 3069 ms 7032 KB Time limit exceeded
10 Halted 0 ms 0 KB -