oj.uz

답안 #257310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257310 2020-08-04T05:45:19 Z 최은수(#5045) Snowy Roads (JOI16_snowy) C++14
15 / 100
 13 ms 1416 KB 
#include"Anyalib.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
static vector<pi>adj[505];
static int n;
static int pa[505],pai[505],dep[505];
static int dp[505];
static vector<int>lst;
static void dfs(int x,int p)
{
    dp[x]=10;
    pa[x]=p;
    for(pi&t:adj[x])
    {
        if(t.fi==p)
            pai[x]=t.se;
        else
            dep[t.fi]=dep[x]+1,dfs(t.fi,x),dp[x]=min(dp[x],dp[t.fi]-1);
    }
    if(dp[x]==0)
    {
        lst.eb(x);
        dp[x]=21;
    }
    return;
}
void InitAnya(int N,int A[],int B[])
{
    n=N;
    for(int i=0;i<n-1;i++)
        adj[A[i]].eb(B[i],i),adj[B[i]].eb(A[i],i);
    dfs(0,-1);
    if(dp[0]!=21)
        lst.eb(0);
    return;
}
static int dis[505];
static int cd[505];
void dfs2(int x,int p)
{
    for(pi&t:adj[x])
        if(t.fi!=p)
            dis[t.fi]=dis[x]+cd[t.se],dfs2(t.fi,x);
    return;
}
void Anya(int C[])
{
    for(int i=0;i<n-1;i++)
        cd[i]=C[i];
    dfs2(0,-1);
    int m=lst.size();
    for(int i=0;i<m;i++)
        for(int j=0;j<9;j++)
            Save(i*9+j,dis[lst[i]]>>j&1);
    for(int i=0;i<n-1;i++)
        Save(500+i,C[i]);
    return;
}
#include"Borislib.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
static vector<pi>adj[505];
static int n;
static int pa[505],pai[505],dep[505];
static int dp[505];
static vector<int>lst;
static void dfs(int x,int p)
{
    dp[x]=10;
    pa[x]=p;
    for(pi&t:adj[x])
    {
        if(t.fi==p)
            pai[x]=t.se;
        else
            dep[t.fi]=dep[x]+1,dfs(t.fi,x),dp[x]=min(dp[x],dp[t.fi]-1);
    }
    if(dp[x]==0)
    {
        lst.eb(x);
        dp[x]=21;
    }
    return;
}
void InitBoris(int N ,int A[],int B[])
{
    n=N;
    for(int i=0;i<n-1;i++)
        adj[A[i]].eb(B[i],i),adj[B[i]].eb(A[i],i);
    dfs(0,-1);
    if(dp[0]!=21)
        lst.eb(0);
    return;
}
int Boris(int city)
{
    int nc=-1;
    int m=lst.size();
    for(int i=0;i<m;i++)
    {
        int x=lst[i];
        int y=city;
        int d=0;
        if(dep[x]>dep[y])
            d++,x=pa[x];
        else
            d++,y=pa[y];
        if(d<=10)
        {
            nc=i;
            break;
        }
    }
    if(nc==-1)
        return 0;
    int get=0;
    for(int i=0;i<9;i++)
        get+=Ask(nc*9+i)*(1<<i);
    nc=lst[nc];
    int C=9;
    while(nc!=city)
    {
        if(dep[nc]>dep[city])
            C++,get-=Ask(500+pai[nc]),nc=pa[nc];
        else
            C++,get+=Ask(500+pai[city]),city=pa[city];
        if(C>=20)
            return -1;
    }
    return get;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 784 KB Output is correct
2 Correct 2 ms 1000 KB Output is correct
3 Correct 3 ms 960 KB Output is correct
4 Correct 4 ms 1024 KB Output is correct
5 Correct 9 ms 1232 KB Output is correct
6 Correct 12 ms 1176 KB Output is correct
7 Correct 7 ms 1184 KB Output is correct
8 Correct 8 ms 1184 KB Output is correct
9 Correct 9 ms 1208 KB Output is correct
10 Correct 8 ms 1308 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1304 KB Output is correct
2 Incorrect 6 ms 1308 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

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

Subtask #4
0 / 45.0

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