oj.uz

Submission #34579

# Submission time Handle Problem Language Result Execution time Memory
34579 2017-11-13T10:20:06 Z Extazy Carnival (CEOI14_carnival) C++14
20 / 100
 66 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());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
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 66 ms 2468 KB Partially correct
2 Partially correct 13 ms 2468 KB Partially correct
3 Partially correct 36 ms 2468 KB Partially correct
4 Partially correct 43 ms 2468 KB Partially correct
5 Partially correct 16 ms 2468 KB Partially correct
6 Correct 0 ms 2468 KB Output is correct
7 Partially correct 46 ms 2468 KB Partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 19 ms 2468 KB Partially correct
2 Partially correct 9 ms 2468 KB Partially correct
3 Partially correct 19 ms 2468 KB Partially correct
4 Partially correct 16 ms 2468 KB Partially correct
5 Partially correct 6 ms 2468 KB Partially correct
6 Correct 6 ms 2468 KB Output is correct
7 Partially correct 6 ms 2468 KB Partially correct

Subtask #3
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2468 KB Output is correct
2 Partially correct 43 ms 2468 KB Partially correct
3 Partially correct 26 ms 2468 KB Partially correct
4 Partially correct 23 ms 2468 KB Partially correct
5 Partially correct 56 ms 2468 KB Partially correct
6 Partially correct 33 ms 2468 KB Partially correct
7 Partially correct 19 ms 2468 KB Partially correct

Subtask #4
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 2468 KB Partially correct
2 Partially correct 63 ms 2468 KB Partially correct
3 Partially correct 19 ms 2468 KB Partially correct
4 Partially correct 19 ms 2468 KB Partially correct
5 Partially correct 39 ms 2468 KB Partially correct
6 Partially correct 49 ms 2468 KB Partially correct
7 Partially correct 33 ms 2468 KB Partially correct

Subtask #5
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 2468 KB Partially correct
2 Partially correct 43 ms 2468 KB Partially correct
3 Partially correct 33 ms 2468 KB Partially correct
4 Partially correct 19 ms 2468 KB Partially correct
5 Partially correct 36 ms 2468 KB Partially correct
6 Partially correct 33 ms 2468 KB Partially correct
7 Partially correct 36 ms 2468 KB Partially correct