oj.uz

Submission #99874

# Submission time Handle Problem Language Result Execution time Memory
99874 2019-03-08T07:24:52 Z TAISA_ None (JOI16_snowy) C++14
20 / 100
 49 ms 1892 KB 
#include <bits/stdc++.h>
#include "Anyalib.h"
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-9;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
vector<vector<P>> G;
vector<int> a,b;
int id;
int n;
void InitAnya(int N,int A[],int B[]){
    n=N;
    a.resize(N-1);
    b.resize(N-1);
    for(int i=0;i<N-1;i++){
        a[i]=A[i];
        b[i]=B[i];
    }
}
void dfs(int i,int p,int sum,int dep){
    if(dep%9==0){
        for(int i=0;i<9;i++){
            if(sum&(1<<i)){
                Save(n+id*9+i,1);
            }
        }
        id++;
    }
    for(auto e:G[i]){
        if(e.first==p)continue;
        Save(e.first,e.second);
        dfs(e.first,i,sum+e.second,dep+1);
    }
}
void Anya(int C[]){
    G.clear();
    G.resize(n);
    id=0;
    for(int i=0;i<n-1;i++){
        G[a[i]].push_back(P(b[i],C[i]));
        G[b[i]].push_back(P(a[i],C[i]));
    }
    dfs(0,-1,0,0);
}
#include <bits/stdc++.h>
#include "Borislib.h"
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-9;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
vector<vector<int>> G;
vector<int> a,b,idx,par,d;
int n,id;
void dfs(int i,int p,int dep){
    if(dep%9==0){
        idx[i]=id;
        id++;
    }
    d[i]=dep;
    par[i]=p;
    for(auto e:G[i]){
        if(e==p)continue;
        dfs(e,i,dep+1);
    }
}
void InitBoris(int N,int A[],int B[]){
    n=N;
    a.resize(N-1);
    b.resize(N-1);
    idx.resize(n,-1);
    par.resize(n,-1);
    d.resize(n);
    G.resize(n);
    id=0;
    for(int i=0;i<N-1;i++){
        a[i]=A[i];
        b[i]=B[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    dfs(0,-1,0);
}
int Boris(int city){
    int v=city;
    int res=0;
    while(1){
        if(d[v]%9==0){
            int k=idx[v];
            for(int i=0;i<9;i++){
                if(Ask(n+9*k+i)){
                    res+=(1<<i);
                }
            }
            break;
        }else{
            res+=Ask(v);
        }
        v=par[v];
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 776 KB Output is correct
2 Correct 5 ms 908 KB Output is correct
3 Correct 7 ms 952 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 11 ms 1048 KB Output is correct
6 Correct 13 ms 1280 KB Output is correct
7 Correct 15 ms 1048 KB Output is correct
8 Correct 10 ms 1048 KB Output is correct
9 Correct 12 ms 1300 KB Output is correct
10 Correct 13 ms 1048 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1280 KB Output is correct
2 Correct 14 ms 1044 KB Output is correct
3 Correct 20 ms 1280 KB Output is correct
4 Correct 18 ms 1308 KB Output is correct
5 Correct 15 ms 1292 KB Output is correct
6 Correct 17 ms 1176 KB Output is correct
7 Correct 19 ms 1292 KB Output is correct
8 Correct 15 ms 1044 KB Output is correct
9 Correct 18 ms 1280 KB Output is correct
10 Correct 15 ms 1288 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 776 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1520 KB Output is correct
2 Correct 49 ms 1892 KB Output is correct
3 Incorrect 6 ms 824 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -