oj.uz

Submission #1106597

# Submission time Handle Problem Language Result Execution time Memory
1106597 2024-10-30T17:27:43 Z Ahmed57 Sphinx's Riddle (IOI24_sphinx) C++17
28.5 / 100
 199 ms 1272 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]);
    }
    queue<int> q;
    set<int> s;
    for(int i = 0;i<n;i++){
        s.insert(i);
    }
    vector<int> col(n,0);
    int d = 0;
    while(!s.empty()){
        q.push((*s.begin()));
        s.erase(s.begin());
        while(!q.empty()){
            int i = q.front();
            q.pop();
            s.erase(i);
        vector<int> v;
        for(auto j:adjj[i]){
            if(s.find(j)==s.end()){
                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++){
                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:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0;i<X.size();i++){
      |                   ~^~~~~~~~~
sphinx.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             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 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
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 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 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 1 ms 336 KB Partially correct
14 Partially correct 3 ms 336 KB Partially correct
15 Partially correct 3 ms 336 KB Partially correct
16 Partially correct 4 ms 336 KB Partially correct
17 Partially correct 4 ms 336 KB Partially correct
18 Partially correct 4 ms 520 KB Partially correct
19 Partially correct 4 ms 336 KB Partially correct
20 Partially correct 5 ms 336 KB Partially correct
21 Partially correct 5 ms 372 KB Partially correct
22 Partially correct 4 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 3 ms 336 KB Partially correct
26 Partially correct 1 ms 336 KB Partially correct
27 Partially correct 1 ms 336 KB Partially correct
28 Partially correct 1 ms 336 KB Partially correct
29 Incorrect 3 ms 336 KB Vertices 31 and 41 do have the same color, but they do not in returned answer
30 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 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
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 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 5 ms 336 KB Partially correct
14 Partially correct 8 ms 336 KB Partially correct
15 Partially correct 6 ms 336 KB Partially correct
16 Partially correct 7 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 6 ms 336 KB Partially correct
20 Partially correct 6 ms 336 KB Partially correct
21 Partially correct 8 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 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 3 ms 336 KB Partially correct
6 Partially correct 3 ms 336 KB Partially correct
7 Partially correct 4 ms 336 KB Partially correct
8 Partially correct 4 ms 336 KB Partially correct
9 Partially correct 4 ms 520 KB Partially correct
10 Partially correct 4 ms 336 KB Partially correct
11 Partially correct 5 ms 336 KB Partially correct
12 Partially correct 5 ms 372 KB Partially correct
13 Partially correct 192 ms 1104 KB Partially correct
14 Partially correct 190 ms 1104 KB Partially correct
15 Partially correct 199 ms 1104 KB Partially correct
16 Partially correct 188 ms 1104 KB Partially correct
17 Partially correct 169 ms 1104 KB Partially correct
18 Partially correct 194 ms 1272 KB Partially correct
19 Partially correct 174 ms 1104 KB Partially correct
20 Partially correct 194 ms 1104 KB Partially correct
21 Partially correct 167 ms 1104 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 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 336 KB Partially correct
12 Partially correct 1 ms 336 KB Partially correct
13 Partially correct 1 ms 336 KB Partially correct
14 Partially correct 3 ms 336 KB Partially correct
15 Partially correct 3 ms 336 KB Partially correct
16 Partially correct 4 ms 336 KB Partially correct
17 Partially correct 4 ms 336 KB Partially correct
18 Partially correct 4 ms 520 KB Partially correct
19 Partially correct 4 ms 336 KB Partially correct
20 Partially correct 5 ms 336 KB Partially correct
21 Partially correct 5 ms 372 KB Partially correct
22 Partially correct 4 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 3 ms 336 KB Partially correct
26 Partially correct 1 ms 336 KB Partially correct
27 Partially correct 1 ms 336 KB Partially correct
28 Partially correct 1 ms 336 KB Partially correct
29 Incorrect 3 ms 336 KB Vertices 31 and 41 do have the same color, but they do not in returned answer
30 Halted 0 ms 0 KB -