| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26160 |
2017-06-28T07:10:36 Z |
tlwpdus |
None (JOI16_snowy) |
C++ |
|
22 ms |
4204 KB |
#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
static int n;
static vector<pii> lis[600];
static pii edg[600];
static const int MD = 11;
static int chk[600];
static int dis[600];
static int lab[600];
static int par[600];
static int pae[600];
static int has[600];
static int ras[600];
static int cnt, ent;
static void dfs(int here, int p) {
int i;
par[here] = p;
dis[here] = 0;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].first;
if (there==p) continue;
dfs(there,here);
has[lis[here][i].second] = ent;
ras[ent] = lis[here][i].second;
lis[here][i].second = ent;
pae[there] = ent++;
dis[here] = max(dis[here],dis[there]+1);
}
if (dis[here]==MD) {
chk[here] = cnt;
lab[cnt++] = here;
dis[here] = -1;
}
}
void InitAnya(int N , int A[] , int B[]) {
n = N;
int i;
for (i=0;i<500;i++) lis[i].clear();
memset(chk,-1,sizeof(chk));
cnt = 0; ent = 0;
for (i=0;i<n-1;i++) {
if (A[i]>B[i]) swap(A[i],B[i]);
lis[A[i]].push_back(pii(B[i],i));
lis[B[i]].push_back(pii(A[i],i));
edg[i] = pii(A[i],B[i]);
}
for (i=0;i<n;i++) sort(lis[i].begin(),lis[i].end());
dfs(0,-1);
}
int sdis[600];
void fdfs(int here, int p, int d, int C[]) {
int i;
sdis[here] = d;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].first;
if (there==p) continue;
fdfs(there,here,d+C[ras[lis[here][i].second]],C);
}
}
void put(int idx, int val) {
int i;
for (i=idx+8;i>=idx;i--) {
Save(i,val%2);
val>>=1;
}
}
void Anya(int C[]) {
int i;
fdfs(0,-1,0,C);
for (i=0;i<cnt;i++) {
put(500+i*9,sdis[lab[i]]);
}
for (i=0;i<n-1;i++) Save(has[i],C[i]);
}
#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
static int n;
static vector<pii> lis[600];
static pii edg[600];
static const int MD = 11;
static int chk[600];
static int dis[600];
static int lab[600];
static int par[600];
static int pae[600];
static int has[600];
static int ras[600];
static int cnt, ent;
static void dfs(int here, int p) {
int i;
par[here] = p;
dis[here] = 0;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].first;
if (there==p) continue;
dfs(there,here);
has[lis[here][i].second] = ent;
ras[ent] = lis[here][i].second;
lis[here][i].second = ent;
pae[there] = ent++;
dis[here] = max(dis[here],dis[there]+1);
}
if (dis[here]==MD) {
chk[here] = cnt;
lab[cnt++] = here;
dis[here] = -1;
}
}
void InitBoris(int N , int A[] , int B[]) {
n = N;
int i;
for (i=0;i<500;i++) lis[i].clear();
memset(chk,-1,sizeof(chk));
for (i=0;i<n-1;i++) {
if (A[i]>B[i]) swap(A[i],B[i]);
lis[A[i]].push_back(pii(B[i],i));
lis[B[i]].push_back(pii(A[i],i));
edg[i] = pii(A[i],B[i]);
}
for (i=0;i<n;i++) sort(lis[i].begin(),lis[i].end());
dfs(0,-1);
}
int bok(int idx) {
int res = 0, i;
for (i=idx;i<idx+9;i++) {
res *= 2;
res += Ask(i);
}
return res;
}
int Boris(int city) {
int p = city, res = 0;
while(p!=0&&chk[p]==-1) {
res += Ask(pae[p]);
p = par[p];
}
if (p) res += bok(500+9*chk[p]);
return res;
}
Compilation message
Anya.cpp: In function 'void dfs(int, int)':
Anya.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
Anya.cpp: In function 'void fdfs(int, int, int, int*)':
Anya.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
Boris.cpp: In function 'void dfs(int, int)':
Boris.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 9 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 9 |
Correct |
9 ms |
4204 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 9 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 10 |
Correct |
22 ms |
4204 KB |
Output is correct |
| 11 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 12 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 13 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 14 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 15 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 16 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 17 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 18 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 19 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 20 |
Correct |
12 ms |
4204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 3 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 4 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 5 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
15 ms |
4204 KB |
Output is correct |
| 9 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 10 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 11 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 12 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 13 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 14 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 15 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 16 |
Correct |
15 ms |
4204 KB |
Output is correct |
| 17 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 18 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 19 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 20 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 21 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 22 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 23 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 24 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 25 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 26 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 27 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 28 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 29 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 30 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 31 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 32 |
Correct |
9 ms |
4204 KB |
Output is correct |
| 33 |
Correct |
19 ms |
4204 KB |
Output is correct |
| 34 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 35 |
Correct |
9 ms |
4204 KB |
Output is correct |
| 36 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 37 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 38 |
Correct |
9 ms |
4204 KB |
Output is correct |
| 39 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 40 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 41 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 42 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 43 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 44 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 45 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 46 |
Correct |
15 ms |
4204 KB |
Output is correct |
| 47 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 48 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 49 |
Correct |
12 ms |
4204 KB |
Output is correct |
| 50 |
Correct |
12 ms |
4204 KB |
Output is correct |
