oj.uz

답안 #476978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476978 2021-09-29T16:06:39 Z nicolaalexandra Amusement Park (JOI17_amusement_park) C++14
0 / 100
 7 ms 1100 KB 
#include <bits/stdc++.h>
#include "Joi.h"
#define DIM 1010
using namespace std;

static vector <int> L[DIM];
static int viz[DIM],val[DIM],idx,n;

/*void MessageBoard (int x, int y){
    return;
}
*/

void dfs (int nod){

    viz[nod] = 1;
    val[nod] = (++idx) % 60; /// ce bit ii atribui

    for (auto vecin : L[nod])
        if (!viz[vecin])
            dfs (vecin);
}

void Joi (int _n, int m, int a[], int b[], long long x, int useless){
    n = _n;
    for (int i=0;i<m;i++){
        a[i]++, b[i]++;
        L[a[i]].push_back(b[i]);
        L[b[i]].push_back(a[i]);
    }

    memset (viz,0,sizeof viz);
    memset (val,0,sizeof val);
    idx = -1;
    dfs (1);

    for (int i=1;i<=n;i++){
        int bit = val[i];
        if (x & (1LL<<bit))
             MessageBoard(i-1,1);
        else  MessageBoard(i-1,0);
    }

}

/*
int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");

    int n,m,x,i,a[100],b[100];

    cin>>n>>m>>x;
    for (i=0;i<m;i++)
        cin>>a[i]>>b[i];

    Joi(n,m,a,b,x,1);

    for (i=1;i<=n;i++)
        cout<<val[i];

    return 0;
}*/

#include <bits/stdc++.h>
#include "Ioi.h"
#define DIM 1010
using namespace std;


static vector <int> L[DIM],edg[DIM];
static int viz[DIM],val[DIM],fth[DIM],s[DIM],f[70],idx,n,cnt;


/*int Move (int dest){
    //return value[dest+1];
}
*/

void add_edge (int x, int y){
    edg[x].push_back(y);
    edg[y].push_back(x);
}

void dfs (int nod){

    viz[nod] = s[nod] = 1;
    val[nod] = (++idx) % 60; /// ce bit ii atribui

    for (auto vecin : L[nod])
        if (!viz[vecin]){
            fth[vecin] = nod;
            add_edge (nod,vecin);
            dfs (vecin);
            s[nod] += s[vecin];
        }
}

void dfs2 (int nod, int tata){
    if (cnt == 60)
        return;
    for (auto vecin : edg[nod])
        if (vecin != tata){
            int ans = Move(vecin-1);

            if (f[val[vecin]] == -1)
                cnt++;
            f[val[vecin]] = ans;

            if (cnt == 60)
                return;

            dfs2 (vecin,nod);
            Move(nod-1); /// trb sa ma intorc inapoi
        }

}

long long Ioi (int _n, int m, int a[], int b[], int start, int val_start, int useless){
    n = _n;
    for (int i=0;i<m;i++){
        a[i]++, b[i]++;
        L[a[i]].push_back(b[i]);
        L[b[i]].push_back(a[i]);
    }

    memset (viz,0,sizeof viz);
    memset (val,0,sizeof val);
    idx = -1;
    dfs (1);

    memset (f,-1,sizeof f);

    start++;

    cnt = 0;
    if (f[val[start]] == -1){
        f[val[start]] = val_start;
        cnt = 1;
    }

    while (s[start] < 60){
        start = fth[start];
        Move(start-1);
    }


    dfs2 (start,0);

    long long sol = 0;
    for (int i=0;i<60;i++)
        if (f[i])
            sol += (1LL<<i);
    return sol;
}


/*int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");




    return 0;
}*/

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 744 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 1100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 756 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 1100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 1100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -