Submission #502139

#	Time	Username	Problem	Language	Result	Execution time	Memory
502139		bigo	Costinland (info1cup19_costinland)	C++14	20 / 100	1 ms	204 KiB

costinland

#include <iostream>
#include <cmath>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#define M 1000000007
#define pii pair<int, int>
typedef long long ll;
using namespace std;
/*
vector<vector<int>>vec;
vector<bool>visit;
vector<int>w;
vector<pair<int, pii>>dp1;
vector<pair<int, pii>>dp2;
vector<int>pre;
pair<int,pii> max1(pair<int, pii>a1, pair<int, pii>a2,bool v1,bool v2) {
    if (a1.first > a2.first)
        return a1;
    else if (a1.first < a2.first)
        return a2;
    else {
        if (v1 and !v2)
            return a1;
        if (v2 and !v1)
            return a2;
        else {
            int tmp1 = abs(a1.second.second - a1.second.first);
            int tmp2 = abs(a2.second.second - a2.second.first);
            if (tmp1 > tmp2)
                return a1;
            else if (tmp2 > tmp1)
                return a2;
            else {
                if (a1.second.second > a2.second.second) {
                    return a1;
                }
                else if (a2.second.second > a1.second.second)
                    return a2;
                else {
                    if (a1.second.first > a2.second.first) {
                        return a2;
                    }
                    else if (a2.second.first > a1.second.first)
                        return a1;
                    else
                        return a1;
                }
            }
        }
    }
}
vector<bool>he;
void dfs(int v) {
    visit[v] = true;
    for (int i = 0; i < vec[v].size(); i++) {
        if (!visit[vec[v][i]]) {
            dfs(vec[v][i]);
        }
        dp2[v] = max1({ dp1[vec[v][i]].first,{w[v],w[v]} }, dp2[v], true, true);
        int val2 = abs(w[vec[v][i]] - w[v]) + dp2[vec[v][i]].first;
        int val = dp1[vec[v][i]].second.second - dp1[vec[v][i]].second.first;
        int val1 = max(dp1[vec[v][i]].second.second, w[v]) - min(dp1[vec[v][i]].second.first, w[v]);
        int val3 = dp1[vec[v][i]].first - val + val1;
        bool tmp123 = he[v];
        if (val1 > val)
            he[v] = true;
        else
            he[v] = false;
        if (val3 >= val2) {
            pair<int, pii> a1 = max1({ val3,{min(dp1[vec[v][i]].second.first, w[v]),max(dp1[vec[v][i]].second.second, w[v])} }, dp1[v], he[i], tmp123);
            if (dp1[v] != a1 )
                pre[v] = vec[v][i];
            dp1[v] = a1;
        }
        else {
            pair <int, pii>a1 = max1({ val2,{min(w[vec[v][i]],w[i]),max(w[vec[v][i]],w[i])} }, dp1[v], he[i], tmp123);
            if (dp1[v] != a1)
                pre[v] = vec[v][i];
            dp1[v] = a1;
        }
    }
}
vector<int>sed;
void bfs(int v) {
    vector<bool>visit(vec.size());
    vector<int>distance1(vec.size());
    distance1[v] = 0;
    for (int i = 0; i < vec.size(); i++) {
        visit[i] = false;
    }
    queue<int>queue1;
    queue1.push(v);
    visit[v] = true;
    while (queue1.empty() == false) {
        sed.push_back(queue1.front());
        int cur = queue1.front();
        queue1.pop();
        for (int i = 0; i < vec[cur].size(); i++) {
            if (visit[vec[cur][i]] == false) {
                visit[vec[cur][i]] = true;
                distance1[vec[cur][i]] = distance1[cur] + 1;
                queue1.push(vec[cur][i]);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    he.resize(n);
    pre.resize(n,-1);
    w.resize(n);
    for (int i = 0; i < n; i++)
        cin >> w[i];
    vec.resize(n);
    visit.resize(n, false);
    vector<int>num(n, 0);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        vec[u].push_back(v);
        num[u]++;
    }
    dp1.resize(n, { -1,{-1,-1} });
    dp2.resize(n, { -1,{-1,-1} });
    for (int i = 0; i < n; i++) {
        if (num[i] == 0) {
            dp1[i] = { 0,{w[i],w[i]} };
            dp2[i] = { 0,{w[i],w[i]} };
            visit[i] = true;
        }
    }
    dfs(0);
    vector<bool>visit1(n, false);
    ll ans = 0;
    bfs(0);
    for (int i = 0; i < n; i++) {
        if (!visit1[sed[i]]) {
            ans += dp1[sed[i]].first;
            int tmp12 = i;
            while (tmp12!=-1) {
                visit1[tmp12] = true;
                tmp12 = pre[tmp12];
            }
        }
    }
    cout << ans;
}*/
/*
int main() {
    int n, k;
    cin >> n >> k;
    multiset<int>set1;
    vector<int>vec(n+k);
    ll sum = 0;
    for (int i = 0; i < n + k; i++) {
        cin >> vec[i];
        set1.insert(vec[i]);
        sum += vec[i];
    }
    for (int i = 0; i < n + k; i++) {
        ll sum1 = sum - vec[i];
        set1.erase(set1.find(vec[i]));
        auto it = set1.begin();
        int a1 = *it;
        ++it;
        int a2 = *it;
        int d = a2 - a1;
        ll sum2 = (2 * a1 + (n - 1) * d) * n / 2;
        if (sum2 == sum1) {
            int cnt = 0;
            for (int j = 0; j < n + k; j++) {
                if (j != i) {
                    cnt++;
                    cout << vec[j];
                    if (cnt != n)
                        cout << " ";
                }
            }
            break;
        }
        set1.insert(vec[i]);
    }
}*/
/*
#include <map>
vector<int>visit;
int main() {
    int n, m, g;
    cin >> n >> m >> g;
    map<int, set<int>>mp;
    vector<int>shor;
    vector<pii>gre;
    for (int i = 0; i < g; i++) {
        int x, y;
        cin >> y >> x;
        mp[y].insert(x);
        shor.push_back(y);
        gre.push_back({ y,x });
    }
    sort(shor.begin(), shor.end());
    sort(gre.begin(), gre.end());
    int q;
    cin >> q;
    vector<pii>vec(g); 
    map<pii, int>con;
    for (int i = 0; i < g; i++) {
        con[gre[i]] = i;
        if (mp[gre[i].first + 1].size() == 0)
            vec[i] = { -1, -1 };
        else {
            auto it = mp[gre[i].first + 1].end();
            --it;
            if (gre[i].second > * it)
                vec[i] = { -1, -1 };
            else
                vec[i] = { gre[i].first + 1,*mp[gre[i].first + 1].lower_bound(gre[i].second) };
        }
    }
    while (q--) {
        int x1, x2, y1, y2;
        cin >> y1 >> x1 >> y2 >> x2;
        pii st;
        if (mp[y1].size() == 0)
            st = { -1, -1 };
        else {
            auto it = mp[y1].end();
            --it;
            if(x1 > * it)
                st = { -1, -1 };
            else
                st = { y1,*mp[y1].lower_bound(x1) };
        }
        bool flag = false;
        if (y1 == y2 and x1 <= x2)
            flag = true;
        if (st.first != -1) {
            while (!flag) {
                if (st.first == y2-1 and st.second <= x2)
                    flag = true;
                else if (vec[con[st]].first == -1)
                    break;
                else if (vec[con[st]].second > x2)
                    break;
                else {
                    st = vec[con[st]];
                }
            }
        }
        if (flag)
            cout << "YES";
        else
            cout << "NO";
        cout << endl;
    }
}*/
/*
#include "grader.h"
#include <map>
void solve(int n){
    map<int, int>his;
    set<int>vec;
    for (int i = 0; i < n; i++) {
        int k = kth(i);
        his[k]++;
        vec.insert(k);
    }
    for (auto u : vec) {
        if (his[u] >= n / 3)
            say_answer(u);
    }
    say_answer(-1);
}*/
int main() {
    int k;
    cin >> k;
    if (k == 1) {
        cout << 2 << " " << 2 << endl;
        cout << "rd" << endl << "r.";
    }
    if (k == 2) {
        cout << 2 << " " << 2 << endl;
        cout << "Xd" << endl << "r.";
    }
    if (k == 3) {
        cout << 2 << " " << 3 << endl;
        cout << "XXd" << endl << "rr.";
    }
    if (k == 4) {
        cout << 2 << " " << 4 << endl;
        cout << "XXXd" << endl << "rrr.";
    }
    if (k == 5) {
        cout << 2 << " " << 5 << endl;
        cout << "XXXXd" << endl << "rrrr.";
    }
    if (k == 6) {
        cout << 3 << " " << 3 << endl;
        cout << "XXd" << endl << "XXd" << endl << "rr.";
    }
    if (k == 7) {
        cout << 3 << " " << 4 << endl;
        cout << "XXXd" << endl << "XXdd" << endl << "rrr.";
    }
    if (k == 8) {
        cout << 3 << " " << 5 << endl;
        cout << "XXXXd" << endl << "XXddd" << endl << "rrrr.";
    }
    if (k == 9) {
        cout << 4 << " " << 4 << endl;
        cout << "XXrd" << endl << "XXXd" << endl <<"Xddd"<< endl << "rrr.";
    }
    if (k == 10) {
        cout << 5 << " " << 4 << endl;
        cout << "XXrd" << endl << "XXXd" << endl << "Xddd" << endl << "Xddd" << endl << "rrr.";
    }
    if (k == 11) {
        cout << 4 << " " << 4 << endl;
        cout << "XXXd" << endl << "XXXd" << endl << "Xddd" << endl << "rrr.";
    }
    if (k == 12) {
        cout << 5 << " " << 4 << endl;
        cout << "XXXd" << endl << "XXXd" << endl << "Xddd" << endl << "Xddd" << endl << "rrr.";
    }
    if (k == 13) {
        cout << 5 << " " << 5 << endl;
        cout << "XXrrd" << endl << "XXXdd" << endl << "ddXdd" << endl << "XdXdd" << endl << "rrrr.";
    }
    if (k == 14) {
        cout << 5 << " " << 5 << endl;
        cout << "XXrrd" << endl << "XXXdd" << endl << "XdXdd" << endl << "XdXdd" << endl << "rrrr.";
    }
    if (k == 15) {
        cout << 5 << " " << 5 << endl;
        cout << "XXXXd" << endl << "XXXrd" << endl << "XdXrd" << endl << "dddrd" << endl << "rrrr.";
    }
    if (k == 16) {
        cout << 5 << " " << 5 << endl;
        cout << "XXXXd" << endl << "XXXXd" << endl << "Xdddd" << endl << "ddddd" << endl << "rrrr.";
    }
    if (k == 17) {
        cout << 5 << " " << 5 << endl;
        cout << "XXXXd" << endl << "XXXXd" << endl << "Xdddd" << endl << "ddddd" << endl << "rrrr.";
    }
    if (k == 18) {
        cout << 5 << " " << 5 << endl;
        cout << "XXXXd" << endl << "XXXXd" << endl << "ddXrd" << endl << "ddddd" << endl << "rrrr.";
    }
    if (k == 19) {
        cout << 5 << " " << 5 << endl;
        cout << "XXXXd" << endl << "XXXXd" << endl << "dddXd" << endl << "ddddd" << endl << "rrrr.";
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80