oj.uz

Submission #1106604

# Submission time Handle Problem Language Result Execution time Memory
1106604 2024-10-30T17:32:28 Z Ahmed57 Sphinx's Riddle (IOI24_sphinx) C++17
28.5 / 100
 210 ms 1104 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]];
        }
        for(auto j:adjj[i]){
            if(s.find(j)!=s.end()){
                q.push(j);
                break;
            }
        }
        }
    }
    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 2 ms 336 KB Partially correct
8 Partially correct 1 ms 508 KB Partially correct
9 Partially correct 1 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 2 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 5 ms 336 KB Partially correct
18 Partially correct 4 ms 336 KB Partially correct
19 Partially correct 4 ms 336 KB Partially correct
20 Partially correct 4 ms 336 KB Partially correct
21 Partially correct 5 ms 336 KB Partially correct
22 Partially correct 4 ms 336 KB Partially correct
23 Partially correct 3 ms 336 KB Partially correct
24 Partially correct 4 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 2 ms 336 KB Vertices 28 and 39 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 2 ms 336 KB Partially correct
7 Partially correct 1 ms 508 KB Partially correct
8 Partially correct 1 ms 336 KB Partially correct
9 Partially correct 1 ms 336 KB Partially correct
10 Partially correct 2 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 7 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 5 ms 336 KB Partially correct
17 Partially correct 5 ms 336 KB Partially correct
18 Partially correct 6 ms 504 KB Partially correct
19 Partially correct 6 ms 336 KB Partially correct
20 Partially correct 5 ms 336 KB Partially correct
21 Partially correct 6 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 5 ms 336 KB Partially correct
9 Partially correct 4 ms 336 KB Partially correct
10 Partially correct 4 ms 336 KB Partially correct
11 Partially correct 4 ms 336 KB Partially correct
12 Partially correct 5 ms 336 KB Partially correct
13 Partially correct 200 ms 1104 KB Partially correct
14 Partially correct 210 ms 1104 KB Partially correct
15 Partially correct 194 ms 1104 KB Partially correct
16 Partially correct 170 ms 1104 KB Partially correct
17 Partially correct 193 ms 1104 KB Partially correct
18 Partially correct 156 ms 1104 KB Partially correct
19 Partially correct 193 ms 1104 KB Partially correct
20 Partially correct 183 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 2 ms 336 KB Partially correct
8 Partially correct 1 ms 508 KB Partially correct
9 Partially correct 1 ms 336 KB Partially correct
10 Partially correct 1 ms 336 KB Partially correct
11 Partially correct 2 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 5 ms 336 KB Partially correct
18 Partially correct 4 ms 336 KB Partially correct
19 Partially correct 4 ms 336 KB Partially correct
20 Partially correct 4 ms 336 KB Partially correct
21 Partially correct 5 ms 336 KB Partially correct
22 Partially correct 4 ms 336 KB Partially correct
23 Partially correct 3 ms 336 KB Partially correct
24 Partially correct 4 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 2 ms 336 KB Vertices 28 and 39 do have the same color, but they do not in returned answer
30 Halted 0 ms 0 KB -