Codeforces Round #647 (Div. 2) – Johnny and Contribution

因为这道题昨晚被zz鄙视了好久,不过我觉得的确不简单啊。唉。

题意

我觉得题意蛮复杂的,然而zz却无法理解为什么我看了这么久都没看懂题。

给出 m 个点和 n 条边,一个长度为 m 的序列表示每个点的权值。现在需要你给出一个标注各个点权值的顺序,要求:

  • 对于每个点,标注的权值和给出的权值相同,否则输出 -1
  • 如果需要给某个点标注权值 x ,那么考虑所有已被标注权值且与该点相邻的点的权值, x 是未被这些权值涉及到的最小正整数。例如, 与该点相邻的点中有三个点已被标注,且分别为 1, 2, 4 ,那么 x = 3

题解

【思路】

有很多说不清的显然。第一个就是,显然,我们应该从已经给出的这个序列入手,按照这个序列数值从小到大的顺序标注。假设我们就根据给出的序列标注,那么在标注的过程中应该检查是否合法。合法的条件就是上面第二条——检查与当前点相邻的所有点。这样的时间复杂度是 O(nm) 的,显然是不可以的。

于是,机智的up主heyuhhh表示,我们可以将这个过程反过来。不是由当前点去check已经标注的点,而是由当前标注的点去推出还未标注的点,有点类似BFS的过程,具体步骤:

  • 将所有点的权值初始化为 1
  • 如果当前点已经被更新过了,且权值与给出的不同,那么返回 -1
  • 如果当前点已经被更新过了,且权值与给出的相同,设该点权值是 x ,那么与之相邻且占用 x 的点的权值更新为 x+1

【代码】

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5;
vector<int> edges[MAXN];
vector<int> blogs[MAXN];
int a[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int m, n; scanf("%d %d", &m, &n);
    for(int i=0; i<n; i++) {
        int x, y; scanf("%d %d", &x, &y);
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    for(int i=0; i<m; i++) {
        int x; scanf("%d", &x);
        blogs[x].push_back(i + 1);
        
    }

    for(int i=1; i<=m; i++) a[i] = 1;

    vector<int> ans;
    for(int i=1; i<=m; i++) {
        for(auto b: blogs[i]) {
            ans.push_back(b);
            if(a[b] != i) {
                printf("-1\n");
                return 0;
            }
            for(auto to: edges[b]) {
                if(a[to] == i) ++a[to];
            }
        }
    }
    for(auto x: ans) printf("%d ", x);
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇