oj.uz

Submission #1106565

# Submission time Handle Problem Language Result Execution time Memory
1106565 2024-10-30T16:37:49 Z Ahmed57 Sphinx's Riddle (IOI24_sphinx) C++17
28.5 / 100
 200 ms 1204 KB 
#include <bits/stdc++.h>
#include "sphinx.h"

 
using namespace std;
int pr[251];
vector<int> adjj[251];
int find(int x){
    if(x==pr[x])return x;
    return pr[x] = find(pr[x]);
}
bool mergegroup(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b)return 0;
    pr[a] = b;
    return 1;
}
vector<int> find_colours(int n,vector<int> X,vector<int> Y){
    for(int i = 0;i<X.size();i++){
        adjj[X[i]].push_back(Y[i]);
        adjj[Y[i]].push_back(X[i]);
    }
    vector<int> col(n,0);
    int d = 0;
    for(int i = n-1;i>=0;i--){
        vector<int> v;
        for(auto j:adjj[i]){
            if(j>i){
                v.push_back(j);
            }
        }
        int sz = v.size();
        int l = 0 , r = sz-1, ans = -1;
        while(l<=r){
            int mid = (l+r)/2;
            vector<int> e(n,n);
            e[i] = -1;
            for(int j = 0;j<=mid;j++){
                e[v[j]] = -1;
            }
            int cnt = 0;
            for(int j = 0;j<n;j++){
                if(e[j]==-1){
                    pr[j] = j;cnt++;
                }else {
                    pr[j] = j;cnt++;
                }
            }
            for(int j = 0;j<X.size();j++){
                if(e[X[j]]==-1&&e[Y[j]]==-1){
                    if(X[j]==i||Y[j]==i)continue;
                    if(col[X[j]]==col[Y[j]])cnt-=mergegroup(X[j],Y[j]);
                }else if(e[X[j]]==n&&e[Y[j]]==n){
                    cnt-=mergegroup(X[j],Y[j]);
                }
            }
            if(cnt==perform_experiment(e)){
                l = mid+1;
            }else {
                ans = mid;
                r = mid-1;
            }
        }
        if(ans==-1){
            col[i] = d++;
        }else{
            col[i] = col[v[ans]];
        }
    }
    return col;
}

Compilation message

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0;i<X.size();i++){
      |                   ~^~~~~~~~~
sphinx.cpp:50:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int j = 0;j<X.size();j++){
      |                           ~^~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #1
1.5 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Partially correct 1 ms 336 KB Partially correct
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Correct 1 ms 336 KB #experiments: 1
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 1 ms 336 KB Partially correct
8 Partially correct 1 ms 336 KB Partially correct
9 Partially correct 1 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 1 ms 336 KB Partially correct
12 Partially correct 1 ms 508 KB Partially correct
13 Partially correct 1 ms 336 KB Partially correct
14 Partially correct 5 ms 336 KB Partially correct
15 Partially correct 4 ms 336 KB Partially correct
16 Partially correct 3 ms 336 KB Partially correct
17 Partially correct 4 ms 336 KB Partially correct
18 Partially correct 3 ms 336 KB Partially correct
19 Partially correct 3 ms 336 KB Partially correct
20 Partially correct 4 ms 336 KB Partially correct
21 Partially correct 4 ms 336 KB Partially correct
22 Partially correct 3 ms 336 KB Partially correct
23 Partially correct 3 ms 336 KB Partially correct
24 Partially correct 3 ms 336 KB Partially correct
25 Partially correct 4 ms 336 KB Partially correct
26 Incorrect 1 ms 336 KB Vertices 20 and 21 do have the same color, but they do not in returned answer
27 Halted 0 ms 0 KB -

Subtask #3
16.5 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Partially correct 1 ms 336 KB Partially correct
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 1 ms 336 KB Partially correct
8 Partially correct 1 ms 336 KB Partially correct
9 Partially correct 1 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 1 ms 508 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 5 ms 336 KB Partially correct
14 Partially correct 7 ms 336 KB Partially correct
15 Partially correct 6 ms 336 KB Partially correct
16 Partially correct 6 ms 336 KB Partially correct
17 Partially correct 5 ms 336 KB Partially correct
18 Partially correct 5 ms 336 KB Partially correct
19 Partially correct 7 ms 504 KB Partially correct
20 Partially correct 6 ms 336 KB Partially correct
21 Partially correct 5 ms 336 KB Partially correct

Subtask #4
10.5 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Partially correct 1 ms 336 KB Partially correct
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 5 ms 336 KB Partially correct
6 Partially correct 4 ms 336 KB Partially correct
7 Partially correct 3 ms 336 KB Partially correct
8 Partially correct 4 ms 336 KB Partially correct
9 Partially correct 3 ms 336 KB Partially correct
10 Partially correct 3 ms 336 KB Partially correct
11 Partially correct 4 ms 336 KB Partially correct
12 Partially correct 4 ms 336 KB Partially correct
13 Partially correct 190 ms 1200 KB Partially correct
14 Partially correct 178 ms 1192 KB Partially correct
15 Partially correct 198 ms 1104 KB Partially correct
16 Partially correct 191 ms 1196 KB Partially correct
17 Partially correct 172 ms 1204 KB Partially correct
18 Partially correct 192 ms 1196 KB Partially correct
19 Partially correct 200 ms 1192 KB Partially correct
20 Partially correct 182 ms 1196 KB Partially correct
21 Partially correct 196 ms 1196 KB Partially correct

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Correct 1 ms 336 KB #experiments: 1
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 1 ms 336 KB Partially correct
7 Partially correct 1 ms 336 KB Partially correct
8 Partially correct 1 ms 336 KB Partially correct
9 Partially correct 1 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 1 ms 336 KB Partially correct
12 Partially correct 1 ms 508 KB Partially correct
13 Partially correct 1 ms 336 KB Partially correct
14 Partially correct 5 ms 336 KB Partially correct
15 Partially correct 4 ms 336 KB Partially correct
16 Partially correct 3 ms 336 KB Partially correct
17 Partially correct 4 ms 336 KB Partially correct
18 Partially correct 3 ms 336 KB Partially correct
19 Partially correct 3 ms 336 KB Partially correct
20 Partially correct 4 ms 336 KB Partially correct
21 Partially correct 4 ms 336 KB Partially correct
22 Partially correct 3 ms 336 KB Partially correct
23 Partially correct 3 ms 336 KB Partially correct
24 Partially correct 3 ms 336 KB Partially correct
25 Partially correct 4 ms 336 KB Partially correct
26 Incorrect 1 ms 336 KB Vertices 20 and 21 do have the same color, but they do not in returned answer
27 Halted 0 ms 0 KB -