QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326679#1411. Communication Jammingtuanlinh1230 0ms13872kbC++204.2kb2024-02-13 18:27:012024-02-13 18:27:01

Judging History

你现在查看的是最新测评结果

  • [2024-02-13 18:27:01]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:13872kb
  • [2024-02-13 18:27:01]
  • 提交

answer

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=200005;
ll l1[maxn], r1[maxn], l2[maxn], r2[maxn];
ll X1[maxn], Y1[maxn], X2[maxn], Y2[maxn];
ll n, to[maxn], pa[maxn], Rank[maxn], l[maxn], r[maxn];
vector <ll> A1[maxn], A2[maxn], H1[maxn], H2[maxn];
vector <pll> req[maxn]; 

ll Find(ll i)
{
    if (pa[i]!=i)
        pa[i]=Find(pa[i]);
    return pa[i];
}

void Union(ll a, ll b)
{
    ll Pa=Find(a), Pb=Find(b);
    if (Pa==Pb) return;
    if (Rank[Pa]<Rank[Pb]) swap(Pa, Pb);
    if (Rank[Pa]==Rank[Pb]) Rank[Pa]++;
    pa[Pb]=Pa, l[Pa]=min(l[Pa], l[Pb]), r[Pa]=max(r[Pa], r[Pb]);
}

void dfs1(ll u)
{
    l1[u]=n, r1[u]=0;
    for (ll v:A1[u])
    {
        if (!l1[v]) dfs1(v);
        l1[u]=min(l1[u], l1[v]), r1[u]=max(r1[u], r1[v]);
    }
}

void dfs2(ll u)
{
    l2[u]=n, r2[u]=0;
    for (ll v:A2[u])
    {
        if (!l2[v]) dfs2(v);
        l2[u]=min(l2[u], l2[v]), r2[u]=max(r2[u], r2[v]);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll m1, m2, q; cin >> n >> m1 >> m2 >> q;
    for (ll i=1; i<=n; i++)
        l1[i]=r1[i]=l2[i]=r2[i]=pa[i]=l[i]=r[i]=i;
    vector <ll> num1, num2; num2.pb(0);
    for (ll i=1; i<=m1; i++)
        cin >> X1[i] >> Y1[i], num1.pb(Y1[i]);
    sort(num1.begin(), num1.end());
    num1.resize(unique(num1.begin(), num1.end())-num1.begin());
    for (ll i=1; i<=m1; i++)
        H1[lower_bound(num1.begin(), num1.end(), Y1[i])-num1.begin()].pb(i+n);
    for (ll i=1; i<n+m1; i++)
    {
        ll t, u, v; cin >> t >> u >> v;
        if (t==1) A1[v+n].pb(u);
        else if (mp(Y1[v], X1[v])>mp(Y1[u], X1[u])) A1[v+n].pb(u+n);
        else A1[u+n].pb(v+n);
    }
    for (ll i=1; i<=m2; i++)
        cin >> X2[i] >> Y2[i], num2.pb(Y2[i]);
    sort(num2.begin(), num2.end(), greater<ll>());
    num2.resize(unique(num2.begin(), num2.end())-num2.begin());
    for (ll i=1; i<=m2; i++)
        H2[lower_bound(num2.begin(), num2.end(), Y2[i], greater<ll>())-num2.begin()].pb(i+n);
    for (ll i=1; i<n+m2; i++)
    {
        ll t, u, v; cin >> t >> u >> v;
        if (t==1) A2[v+n].pb(u);
        else if (mp(Y2[v], X2[v])<mp(Y2[u], X2[u])) A2[v+n].pb(u+n);
        else A2[u+n].pb(v+n);
    }
    for (ll i=1; i<=n+m1; i++)
        if (!l1[i]) dfs1(i);
    vector <pair<pll, ll>> order;
    for (ll i=1; i<=m1; i++)
        order.pb({{Y1[i], X1[i]}, i+n});
    sort(order.begin(), order.end());
    for (ll i=0; i<order.size(); i++)
    {
        ll id=order[i].se;
        if (!r[id]) continue;
        vector <pll> c;
        for (ll j:A1[id])
            if (r1[j]) c.pb({l[Find(l1[j])], r[Find(r1[j])]});
        sort(c.begin(), c.end());
        for (ll i=0; i+1<c.size(); i++)
        {
            // if (c[i].se+1!=c[i+1].fi)
            // {
            // }
            req[id].pb({c[i].se, c[i+1].fi}), Union(c[i].se, c[i+1].fi);
        }
        if (Find(l1[id])!=Find(r1[id]))
        {
            cout << id << "\n";
            function <void(int)> dfs=[&](ll u)
            {
                cout << u << " " << l1[u] << " " << r1[u] << " " << l[Find(l1[u])] << " " << r[Find(r1[u])] << "\n";
                for (ll v:A1[u]) dfs(v);
            }; dfs(id);
            exit(0);
        }
    }
    for (ll i=1; i<=n+m2; i++)
        if (!l2[i]) dfs2(i);
    ll k1=num1.size(), k2=num2.size();
    auto in=[&](ll a, ll b) {return r[Find(a)]>=b;};
    auto insert=[&](ll a, ll b)
    {
        while (r[Find(a)]<b) 
            a=r[Find(a)]+1, Union(a, a-1);
    };
    for (ll i=1; i<=n; i++) pa[i]=l[i]=r[i]=i, Rank[i]=0;
    for (ll i=k1, ptr=0; i>=0; i--)
    {
        for (ll j:H1[i]) for (auto [l, r]:req[j])
        {
            while (!in(l, r))
            {
                ptr++;
                for (ll j:H2[ptr]) 
                    if (r2[j]) insert(l2[j], r2[j]);
            }
        }
        to[i]=ptr;
    }
    for (ll i=1; i<=q; i++)
    {
        ll a; cin >> a;
        ll pos=upper_bound(num1.begin(), num1.end(), a)-num1.begin();
        cout << num2[to[pos]] << "\n";
    }
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 13872kb

input:

100 99 99 100
40 71
79 29
1 20
88 54
70 38
77 30
31 12
79 81
84 34
17 65
68 57
40 2
14 22
56 3
15 17
11 75
36 77
52 7
30 91
82 13
19 64
44 14
63 41
38 18
99 84
22 49
68 39
64 63
99 93
8 48
66 10
6 83
45 35
94 37
58 87
89 15
71 4
75 60
59 42
74 62
56 59
82 73
90 24
76 95
36 21
91 67
33 31
13 79
20 50...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '-98', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%