oj.uz

Submission #1106612

# Submission time Handle Problem Language Result Execution time Memory
1106612 2024-10-30T17:36:59 Z Ahmed57 Sphinx's Riddle (IOI24_sphinx) C++17
28.5 / 100
 200 ms 1992 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]);
    }
    stack<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()));
        while(!q.empty()){
            int i = q.top();
            q.pop();
            if(s.find(i)==s.end())continue;
            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);
            }
        }
        }
    }
    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 2 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 2 ms 336 KB Partially correct
11 Partially correct 1 ms 336 KB Partially correct
12 Partially correct 2 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 4 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 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 4 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 4 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 27 and 46 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 2 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 2 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 6 ms 336 KB Partially correct
14 Partially correct 8 ms 336 KB Partially correct
15 Partially correct 5 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 336 KB Partially correct
19 Partially correct 5 ms 336 KB Partially correct
20 Partially correct 6 ms 336 KB Partially correct
21 Partially correct 7 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 4 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 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 4 ms 336 KB Partially correct
13 Partially correct 174 ms 1496 KB Partially correct
14 Partially correct 187 ms 1268 KB Partially correct
15 Partially correct 192 ms 1992 KB Partially correct
16 Partially correct 195 ms 1324 KB Partially correct
17 Partially correct 179 ms 1608 KB Partially correct
18 Partially correct 171 ms 1572 KB Partially correct
19 Partially correct 181 ms 1320 KB Partially correct
20 Partially correct 200 ms 1264 KB Partially correct
21 Partially correct 164 ms 1536 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 2 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 2 ms 336 KB Partially correct
11 Partially correct 1 ms 336 KB Partially correct
12 Partially correct 2 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 4 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 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 4 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 4 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 27 and 46 do have the same color, but they do not in returned answer
30 Halted 0 ms 0 KB -