oj.uz

답안 #1106612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106612 2024-10-30T17:36:59 Z Ahmed57 스핑크스 (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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #1
1.5 / 3.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -