Codeforces Round 1003 (Div. 4) E

发表于 分类于 ， 阅读次数：

E. Skibidus and Rizz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>

using namespace std;
#define all(a) a.begin(),a.end()
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> vll;
typedef pair<int,int> PII;

int T = 1;

void solve() {
    int n,m,k;
    cin>>n>>m>>k;
    int minn=min(n,m);
    int maxx=max(n,m);
    if(maxx<k){
        cout<<-1<<'\n';return ;
    }
    maxx-=k;
    if(maxx>minn){
        cout<<-1<<'\n';return ;
    }
    else if(minn-maxx>k){
        cout<<-1<<'\n';return ;
    }
    if(n>m){
        rep(i,1,k)cout<<'0';
        rep(i,1,maxx)cout<<"10";
        rep(i,1,minn-maxx)cout<<'1';
    }else{
        rep(i,1,k)cout<<'1';
        rep(i,1,maxx)cout<<"01";
        rep(i,1,minn-maxx)cout<<'0';
    }cout<<'\n';
}

int main() {
    #ifdef Online_Judge
    freopen("INPUT.in", "r", stdin); 
    freopen("OUTPUT.out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    while (T--) solve();
}

F. Skibidus and Slay

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>

using namespace std;
#define all(a) a.begin(),a.end()
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> vll;
typedef pair<int,int> PII;

const int N=2e5+5,M=6000+5;
const int Size=1e9;
const ll inf=1e18;
const ll MOD=998244353;
int T = 1;

int n;

void solve() {
    
    cin>>n;
    vi p(n+1);
    vii g(n+1);
    vi ans(n+1);
    rep(i,1,n)cin>>p[i];
    rep(i,1,n-1){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        if(p[u]==p[v])ans[p[u]]=1;
    }
    vi near(n+1);
    rep(i,1,n){
        int f=0;
        for(auto u:g[i])if(p[u]==p[i])ans[p[i]]=1;
        for(auto u:g[i]){
            if(near[p[u]])ans[p[u]]=1;
            near[p[u]]++;
        }
        for(auto u:g[i])near[p[u]]--;
    }
    rep(i,1,n)cout<<ans[i];
    cout<<'\n';
}

int main() {
    #ifdef Online_Judge
    freopen("INPUT.in", "r", stdin); 
    freopen("OUTPUT.out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    while (T--) solve();
}