oj.uz

Submission #5987

# Submission time Handle Problem Language Result Execution time Memory
5987 2014-06-11T14:50:35 Z model_code 한자 끝말잇기 (JOI14_kanji) C++
100 / 100
 262 ms 13540 KB 
#include <cstdlib>
#include <cstdio>
#include <cstring> 
#include <vector>
#include <algorithm>
#include <queue>
#include "Annalib.h"

using namespace std;

#define NMAX 310
#define MMAX 90010
#define QMAX 100
#define KMAX 15
#define UNDEF -1

static void wf(int N,int M, int A[],int B[], long long C[],long long dist[NMAX][NMAX],int next[NMAX][NMAX]){
  for(int i=0;i<N;i++){
    fill(dist[i],dist[i]+N,UNDEF);
    fill(next[i],next[i]+N,-1);
    for(int j=0;j<N;j++){
      if(i==j){dist[i][j]=0;}
    }
  }
  for(int i=0;i<M;i++){
    dist[A[i]][B[i]]=C[i];
    next[A[i]][B[i]]=i;
  }
  for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        if(dist[i][k]==UNDEF||dist[k][j]==UNDEF){continue;}
        if(dist[i][j]==UNDEF||dist[i][j]>dist[i][k]+dist[k][j]){
          dist[i][j]=dist[i][k]+dist[k][j];
          next[i][j]=next[i][k];
        }
  }}}
}

static long long a[100][10];
static long long b[100][10];
static long long c[100][10];
static bool exist_path[100][10];

bool compare_path(int j,int k,int i){
  return (a[j][k]+b[j][k]+c[j][k])<(a[j][i]+b[j][i]+c[j][i]);
}

int Anna(int N,int M,int A[],int B[],long long C[],int Q,int S[],int T[],int K,int U[]){
  
  long long brunoC[MMAX]; memcpy(brunoC,C,sizeof(long long)*M);
  for(int l=0;l<K;l++){brunoC[U[l]]=UNDEF;}
  
  long long dist[NMAX][NMAX];
  int next[NMAX][NMAX];
  wf(N,M,A,B,brunoC,dist,next);
  
  for(int j=0;j<Q;j++){
    for(int k=0;k<K+1;k++){
      exist_path[j][k]=true;
      if(k==0){
        a[j][k]=dist[S[j]][T[j]];
        b[j][k]=0;
        c[j][k]=0;
      }
      else{
        a[j][k]=dist[S[j]][A[U[k-1]]];
        b[j][k]=dist[B[U[k-1]]][T[j]];
        c[j][k]=C[U[k-1]];
      }
      if(a[j][k]==UNDEF||b[j][k]==UNDEF){exist_path[j][k]=false;}
    }
  }

  int head=0;
  int data_max[QMAX];fill(data_max,data_max+QMAX,0);
  int data[QMAX];fill(data,data+QMAX,0);
  int path[QMAX];fill(path,path+QMAX,0);
  
  for(int k=1;k<K+1;k++){
    
    for(int j=0;j<Q;j++){
      if(!exist_path[j][k]){continue;}
      if(!exist_path[j][path[j]]){path[j]=k;continue;}
      data_max[head+path[j]]++;
      if(compare_path(j,k,path[j])){
        data[head+path[j]]++;
        path[j]=k;
      }
    }
    head+=k;
  }
  
  unsigned long long XX=0;
  
  for(int i=head-1;i>=0;i--){
    if(data_max[i]!=0){
      XX=XX*(data_max[i]+1)+data[i];
    }
  }
  while(XX>0){
    Tap(XX%2);
    XX=XX/2;
  }
}
#include <cstdlib>
#include <cstdio>
#include <cstring> 
#include <vector>
#include <algorithm>
#include <queue>
#include "Brunolib.h"

using namespace std;

#define NMAX 310
#define MMAX 90010
#define QMAX 100
#define KMAX 15
#define UNDEF -1

static void wf(int N,int M, int A[],int B[], long long C[],long long dist[NMAX][NMAX],int next[NMAX][NMAX]){
  for(int i=0;i<N;i++){
    fill(dist[i],dist[i]+N,UNDEF);
    fill(next[i],next[i]+N,-1);
    for(int j=0;j<N;j++){
      if(i==j){dist[i][j]=0;}
    }
  }
  for(int i=0;i<M;i++){
    dist[A[i]][B[i]]=C[i];
    next[A[i]][B[i]]=i;
  }
  for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        if(dist[i][k]==UNDEF||dist[k][j]==UNDEF){continue;}
        if(dist[i][j]==UNDEF||dist[i][j]>dist[i][k]+dist[k][j]){
          dist[i][j]=dist[i][k]+dist[k][j];
          next[i][j]=next[i][k];
        }
  }}}
}
void Travel(int qno,int N,int A[],int B[],int S,int T,int next[NMAX][NMAX]){
  while(S!=T){
    Answer(next[S][T]);
    S=B[next[S][T]];
  }
}

static long long a[100][10];
static long long b[100][10];
static long long c[100][10];
static bool exist_path[100][10];

static int path1;
static int path2;
bool compare(int i,int j){
  return (a[i][path1]+b[i][path1]-a[i][path2]-b[i][path2])<(a[j][path1]+b[j][path1]-a[j][path2]-b[j][path2]);
}

int Bruno(int N,int M,int A[],int B[],long long C[],int Q,int S[],int T[],int K,int U[],int L,int X[]){
  
  long long dist[NMAX][NMAX];
  int next[NMAX][NMAX];
  wf(N,M,A,B,C,dist,next);

  unsigned long long XX=0;
  for(int i=L-1;i>=0;i--){
    XX=(XX<<1)+X[i];
  }
  
  for(int j=0;j<Q;j++){
    for(int k=0;k<K+1;k++){
      exist_path[j][k]=true;
      if(k==0){
        a[j][k]=dist[S[j]][T[j]];
        b[j][k]=0;
        c[j][k]=0;
      }
      else{
        a[j][k]=dist[S[j]][A[U[k-1]]];
        b[j][k]=dist[B[U[k-1]]][T[j]];
        c[j][k]=C[U[k-1]];
      }
      if(a[j][k]==UNDEF||b[j][k]==UNDEF){exist_path[j][k]=false;}
    }
  }
  
  int head=0;
  int data_max[QMAX];fill(data_max,data_max+QMAX,0);
  int data[QMAX];fill(data,data+QMAX,0);
  int path[QMAX];fill(path,path+QMAX,0);
  
  for(int k=1;k<K+1;k++){
    vector<vector<int> > vecs(K+1);
    for(int j=0;j<Q;j++){
      if(!exist_path[j][k]){continue;}
      if(!exist_path[j][path[j]]){path[j]=k;continue;}
      data_max[head+path[j]]++;
      vecs[path[j]].push_back(j);
    }
    for(int i=0;i<k;i++){
      if(vecs[i].size()!=0){
        data[head]=XX%(data_max[head]+1);
        XX=XX/(vecs[i].size()+1);
        path1 = k;
        path2 = i;
        sort(vecs[i].begin(),vecs[i].end(),compare);
        for(int j=0;j<vecs[i].size();j++){
          if(j<data[head]){path[vecs[i][j]]=k;}
        }
      }
      head++;
    }
  }

  for(int j=0;j<Q;j++){
    path[j]--;
    if(path[j]!=-1){
      Travel(j,N,A,B,S[j],A[U[path[j]]],next);
      Answer(U[path[j]]);
      Travel(j,N,A,B,B[U[path[j]]],T[j],next);
    }
    else{
      Travel(j,N,A,B,S[j],T[j],next);
    }
    Answer(-1);
  }
}

Compilation message

Anna.cpp: In function 'int Anna(int, int, int*, int*, long long int*, int, int*, int*, int, int*)':
Anna.cpp:105:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Bruno.cpp: In function 'int Bruno(int, int, int*, int*, long long int*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:105:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<vecs[i].size();j++){
                      ^
Bruno.cpp:125:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 13536 KB Output is correct - L = 19
2 Correct 78 ms 13532 KB Output is correct - L = 20
3 Correct 84 ms 13536 KB Output is correct - L = 1
4 Correct 66 ms 13532 KB Output is correct - L = 17
5 Correct 66 ms 13532 KB Output is correct - L = 23
6 Correct 65 ms 13532 KB Output is correct - L = 19
7 Correct 58 ms 13540 KB Output is correct - L = 9
8 Correct 102 ms 13536 KB Output is correct - L = 4
9 Correct 109 ms 13532 KB Output is correct - L = 7
10 Correct 106 ms 13532 KB Output is correct - L = 4
11 Correct 72 ms 13532 KB Output is correct - L = 4
12 Correct 228 ms 13540 KB Output is correct - L = 0
13 Correct 81 ms 13524 KB Output is correct - L = 5
14 Correct 81 ms 13540 KB Output is correct - L = 0

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 13532 KB Output is correct - L = 41
2 Correct 66 ms 13536 KB Output is correct - L = 50
3 Correct 78 ms 13528 KB Output is correct - L = 0
4 Correct 69 ms 13536 KB Output is correct - L = 24
5 Correct 88 ms 13532 KB Output is correct - L = 45
6 Correct 81 ms 13528 KB Output is correct - L = 57
7 Correct 99 ms 13536 KB Output is correct - L = 1
8 Correct 86 ms 13532 KB Output is correct - L = 1
9 Correct 55 ms 13532 KB Output is correct - L = 61
10 Correct 52 ms 13524 KB Output is correct - L = 61
11 Correct 55 ms 13536 KB Output is correct - L = 61
12 Correct 86 ms 13532 KB Output is correct - L = 0
13 Correct 248 ms 13536 KB Output is correct - L = 0
14 Correct 75 ms 13536 KB Output is correct - L = 47
15 Correct 89 ms 13532 KB Output is correct - L = 12
16 Correct 105 ms 13532 KB Output is correct - L = 22
17 Correct 105 ms 13532 KB Output is correct - L = 20
18 Correct 106 ms 13524 KB Output is correct - L = 37
19 Correct 92 ms 13528 KB Output is correct - L = 31
20 Correct 105 ms 13536 KB Output is correct - L = 0
21 Correct 122 ms 13528 KB Output is correct - L = 0
22 Correct 58 ms 13532 KB Output is correct - L = 60
23 Correct 65 ms 13532 KB Output is correct - L = 60
24 Correct 62 ms 13528 KB Output is correct - L = 60

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 13528 KB Output is correct - L = 41
2 Correct 66 ms 13528 KB Output is correct - L = 50
3 Correct 75 ms 13536 KB Output is correct - L = 0
4 Correct 62 ms 13532 KB Output is correct - L = 24
5 Correct 105 ms 13536 KB Output is correct - L = 45
6 Correct 89 ms 13536 KB Output is correct - L = 57
7 Correct 86 ms 13532 KB Output is correct - L = 1
8 Correct 89 ms 13528 KB Output is correct - L = 1
9 Correct 76 ms 13528 KB Output is correct - L = 61
10 Correct 78 ms 13532 KB Output is correct - L = 61
11 Correct 55 ms 13528 KB Output is correct - L = 61
12 Correct 92 ms 13528 KB Output is correct - L = 0
13 Correct 252 ms 13528 KB Output is correct - L = 0
14 Correct 86 ms 13532 KB Output is correct - L = 47
15 Correct 86 ms 13528 KB Output is correct - L = 12
16 Correct 95 ms 13532 KB Output is correct - L = 22
17 Correct 112 ms 13532 KB Output is correct - L = 20
18 Correct 119 ms 13532 KB Output is correct - L = 37
19 Correct 102 ms 13532 KB Output is correct - L = 31
20 Correct 122 ms 13528 KB Output is correct - L = 0
21 Correct 145 ms 13536 KB Output is correct - L = 0
22 Correct 52 ms 13536 KB Output is correct - L = 60
23 Correct 62 ms 13536 KB Output is correct - L = 60
24 Correct 62 ms 13532 KB Output is correct - L = 60

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 13528 KB Output is correct - L = 41
2 Correct 62 ms 13532 KB Output is correct - L = 50
3 Correct 62 ms 13528 KB Output is correct - L = 0
4 Correct 55 ms 13532 KB Output is correct - L = 24
5 Correct 89 ms 13536 KB Output is correct - L = 45
6 Correct 105 ms 13540 KB Output is correct - L = 57
7 Correct 81 ms 13536 KB Output is correct - L = 1
8 Correct 81 ms 13536 KB Output is correct - L = 1
9 Correct 58 ms 13536 KB Output is correct - L = 61
10 Correct 66 ms 13528 KB Output is correct - L = 61
11 Correct 65 ms 13532 KB Output is correct - L = 61
12 Correct 81 ms 13536 KB Output is correct - L = 0
13 Correct 262 ms 13532 KB Output is correct - L = 0
14 Correct 84 ms 13532 KB Output is correct - L = 47
15 Correct 86 ms 13536 KB Output is correct - L = 12
16 Correct 105 ms 13532 KB Output is correct - L = 22
17 Correct 135 ms 13536 KB Output is correct - L = 20
18 Correct 125 ms 13536 KB Output is correct - L = 37
19 Correct 78 ms 13528 KB Output is correct - L = 31
20 Correct 99 ms 13528 KB Output is correct - L = 0
21 Correct 122 ms 13528 KB Output is correct - L = 0
22 Correct 55 ms 13532 KB Output is correct - L = 60
23 Correct 62 ms 13536 KB Output is correct - L = 60
24 Correct 59 ms 13532 KB Output is correct - L = 60

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 13532 KB Output is correct - L = 41
2 Correct 58 ms 13536 KB Output is correct - L = 50
3 Correct 62 ms 13536 KB Output is correct - L = 0
4 Correct 62 ms 13536 KB Output is correct - L = 24
5 Correct 86 ms 13524 KB Output is correct - L = 45
6 Correct 81 ms 13532 KB Output is correct - L = 57
7 Correct 78 ms 13528 KB Output is correct - L = 1
8 Correct 81 ms 13528 KB Output is correct - L = 1
9 Correct 59 ms 13532 KB Output is correct - L = 61
10 Correct 55 ms 13536 KB Output is correct - L = 61
11 Correct 58 ms 13536 KB Output is correct - L = 61
12 Correct 81 ms 13532 KB Output is correct - L = 0
13 Correct 259 ms 13532 KB Output is correct - L = 0
14 Correct 81 ms 13524 KB Output is correct - L = 47
15 Correct 89 ms 13528 KB Output is correct - L = 12
16 Correct 98 ms 13532 KB Output is correct - L = 22
17 Correct 114 ms 13536 KB Output is correct - L = 20
18 Correct 111 ms 13532 KB Output is correct - L = 37
19 Correct 98 ms 13524 KB Output is correct - L = 31
20 Correct 95 ms 13540 KB Output is correct - L = 0
21 Correct 114 ms 13532 KB Output is correct - L = 0
22 Correct 72 ms 13528 KB Output is correct - L = 60
23 Correct 72 ms 13524 KB Output is correct - L = 60
24 Correct 62 ms 13528 KB Output is correct - L = 60