Submission #1650382


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

const int N = 100000;
const ll INF = LLONG_MAX/3;

vector<int> G[N];
vector<int> ew;
void dfs(int v)
{
    ew.pb(v);
    for(int c:G[v]) dfs(c);
    ew.pb(v);
}

int main()
{
    int n;
    scanf(" %d", &n);
    vector<int> a(n);
    rep(i,n) scanf(" %d", &a[i]);

    vector<bool> candidate(n,true);
    rep(i,n-1)
    {
        int s,t;
        scanf(" %d %d", &s, &t);
        G[s].pb(t);
        candidate[t] = false;
    }

    int root = 0;
    rep(i,n)if(candidate[i]) root = i;
    dfs(root);

    vector<ll> val(n,INF);
    set<int> v;

    vector<int> ct(n);
    rep(i,ew.size())
    {
        int id = ew[i];
        if(ct[id]==0)
        {
            auto itr = v.lower_bound(a[id]);
            if(itr!=v.end())
            {
                int x = *itr;
                if(abs(a[id]-x)<abs(a[id]-val[id]) || (abs(a[id]-x)==abs(a[id]-val[id]) && x<val[id])) val[id] = x;
            }
            if(itr!=v.begin())
            {
                --itr;
                int x = *itr;
                if(abs(a[id]-x)<abs(a[id]-val[id]) || (abs(a[id]-x)==abs(a[id]-val[id]) && x<val[id])) val[id] = x;
            }
        }
        else v.insert(a[id]);
        ++ct[id];
    }

    v.clear();
    reverse(all(ew));
    ct = vector<int>(n,0);
    rep(i,ew.size())
    {
        int id = ew[i];
        if(ct[id]==0)
        {
            auto itr = v.lower_bound(a[id]);
            if(itr!=v.end())
            {
                int x = *itr;
                if(abs(a[id]-x)<abs(a[id]-val[id]) || (abs(a[id]-x)==abs(a[id]-val[id]) && x<val[id])) val[id] = x;
            }
            if(itr!=v.begin())
            {
                --itr;
                int x = *itr;
                if(abs(a[id]-x)<abs(a[id]-val[id]) || (abs(a[id]-x)==abs(a[id]-val[id]) && x<val[id])) val[id] = x;
            }
        }
        else v.insert(a[id]);
        ++ct[id];
    }

    rep(i,n) printf("%lld\n", val[i]==INF?-1:val[i]);
    return 0;
}

Submission Info

Submission Time
Task I - 支配と友好
User imulan
Language C++14 (GCC 5.4.1)
Score 200
Code Size 2568 Byte
Status AC
Exec Time 154 ms
Memory 17708 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:30:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d", &n);
                     ^
./Main.cpp:32:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     rep(i,n) scanf(" %d", &a[i]);
                                 ^
./Main.cpp:38:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d %d", &s, &t);
                                ^

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 45
Set Name Test Cases
All sample01, sample02, sample03, binary00, binary01, binary02, binary03, hand00, line00, line01, line02, random00, random01, random02, random03, random04, random05, random06, random07, random08, sample01, sample02, sample03, star00, star01, star02, ternary00, ternary01, ternary02, ternary03, thin00, thin01, thin02, thin03, thin04, thin05, thin06, thin07, uniform00, uniform01, uniform02, uniform03, uniform04, uniform05, uniform06
Case Name Status Exec Time Memory
binary00 AC 67 ms 7156 KB
binary01 AC 102 ms 7412 KB
binary02 AC 147 ms 11968 KB
binary03 AC 148 ms 12204 KB
hand00 AC 94 ms 15916 KB
line00 AC 62 ms 13428 KB
line01 AC 83 ms 13556 KB
line02 AC 125 ms 17708 KB
random00 AC 60 ms 7160 KB
random01 AC 68 ms 7288 KB
random02 AC 82 ms 7288 KB
random03 AC 103 ms 7544 KB
random04 AC 135 ms 10092 KB
random05 AC 146 ms 11664 KB
random06 AC 148 ms 11972 KB
random07 AC 148 ms 12080 KB
random08 AC 149 ms 12208 KB
sample01 AC 2 ms 2560 KB
sample02 AC 2 ms 2560 KB
sample03 AC 2 ms 2560 KB
star00 AC 54 ms 6008 KB
star01 AC 91 ms 6264 KB
star02 AC 135 ms 10928 KB
ternary00 AC 65 ms 6644 KB
ternary01 AC 101 ms 6900 KB
ternary02 AC 145 ms 11460 KB
ternary03 AC 147 ms 11692 KB
thin00 AC 69 ms 9460 KB
thin01 AC 67 ms 8180 KB
thin02 AC 106 ms 9844 KB
thin03 AC 105 ms 8436 KB
thin04 AC 151 ms 14276 KB
thin05 AC 148 ms 12992 KB
thin06 AC 154 ms 14508 KB
thin07 AC 150 ms 13228 KB
uniform00 AC 145 ms 11312 KB
uniform01 AC 153 ms 11632 KB
uniform02 AC 149 ms 11380 KB
uniform03 AC 153 ms 11276 KB
uniform04 AC 151 ms 11108 KB
uniform05 AC 146 ms 11104 KB
uniform06 AC 141 ms 10976 KB