oj.uz

답안 #34578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34578 2017-11-13T10:19:29 Z Extazy 사육제 (CEOI14_carnival) C++14
0 / 100
 19 ms 2468 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 157;

int n,parents[N];
int p[N];
map < int, int > code;
bool asked[N][N];
int answer[N][N];
int f[N];
int qcnt;

int find(int x) {
    while(x!=parents[x]) {
        parents[x]=parents[parents[x]];
        x=parents[x];
    }
    return x;
}

bool join(int x, int y) {
    //printf("Here\n");
    int fx=find(x),fy=find(y);
    //printf("Here\n");
    if(fx==fy) return false;
    if(rand()%2==0) parents[fx]=fy;
    else parents[fy]=fx;
    return true;
}

int ask(int x, int y) {
    if(find(x)==find(y)) return 1;
    ++qcnt;
    printf("2 %d %d\n", x, y);
    fflush(stdout);
    int ret;
    scanf("%d", &ret);
    asked[x][y]=asked[y][x]=true;
    answer[x][y]=answer[y][x]=ret;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j;
    vector < pair < int, int > > prs;

    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        parents[i]=i;
    }

    for(i=1;i<=n;i++) {
        for(j=i+1;j<=n;j++) {
            prs.push_back(make_pair(i,j));
        }
    }

    random_shuffle(prs.begin(),prs.end());

    for(i=0;i<(int)(prs.size()) && qcnt<3500;i++) {
        int x=prs[i].first,y=prs[i].second;
        int ans=ask(x,y);
        if(ans==1) join(x,y);
    }

    for(i=1;i<=n;i++) f[i]=find(i),p[i]=f[i];

    sort(p+1,p+1+n);
    code[p[1]]=1;
    for(i=2;i<=n;i++) if(p[i]!=p[i-1]) code[p[i]]=code[p[i-1]]+1;

    printf("0");
    for(i=1;i<=n;i++) {
        printf(" %d", code[f[i]]);
    }
    printf("\n");
    fflush(stdout);

    return 0;
}

Compilation message

carnival.cpp: In function 'int ask(int, int)':
carnival.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ret);
                      ^
carnival.cpp: In function 'int main()':
carnival.cpp:52:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 2468 KB Integer 12 violates the range [1, 11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2468 KB Output is correct
2 Incorrect 9 ms 2468 KB Integer 32 violates the range [1, 28]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2468 KB Output is correct
2 Correct 19 ms 2468 KB Output is correct
3 Incorrect 3 ms 2468 KB Integer 70 violates the range [1, 58]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2468 KB Output is correct
2 Correct 19 ms 2468 KB Output is correct
3 Incorrect 16 ms 2468 KB Integer 139 violates the range [1, 120]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2468 KB Output is correct
2 Incorrect 9 ms 2468 KB Integer 19 violates the range [1, 17]
3 Halted 0 ms 0 KB -