Submission #34579

#	Time	Username	Problem	Language	Result	Execution time	Memory
34579		Extazy	Carnival (CEOI14_carnival)	C++14	20 / 100	66 ms	2468 KiB

carnival

#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 (stderr)

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 / 20
• Subtask 2: 4 / 20
• Subtask 3: 4 / 20
• Subtask 4: 4 / 20
• Subtask 5: 4 / 20