제출 #1055642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055642		LeaRouse	Split the Attractions (IOI19_split)	C++14	0 / 100	2 ms	3420 KiB

split

#include <bits/stdc++.h>
#include "split.h"
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const int MAX=1e5+5;
const int MOD=1e8+7;
int R[MAX];
int A[MAX];
int B[MAX];
int C[MAX];
int D[MAX];
map<string,int>m;
vector<int>v[MAX];
bool vis[MAX];
int cont=0;
bool viss[MAX];
void dfs(int u){
    A[cont]=u;
    cont++;
    vis[u]=true;
    for(auto it:v[u]){
        if(vis[it]) continue;
        D[it]=D[u]+1;
        dfs(it);
        C[u]+=C[it];
    }
    C[u]++;
}
int miau=1;
vector<int>res(MAX);
void dfs1(int u){
    viss[u]=1;
    res[u]=miau;
    for(auto it:v[u]){
        if(viss[it])    continue;
        dfs1(it);
    }

}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    int m=p.size();
    if(m==N-1){
        dfs(0);
        for(int i=0;i<m;i++){
            if(D[p[i]]<D[q[i]])   swap(p[i],q[i]);
            if(C[p[i]]>=a and N-C[p[i]]>=b){
                viss[q[i]]=1;
                dfs1(p[i]);
                viss[q[i]]=0;
                miau++;
                dfs1(q[i]);
                break;
            }
            if(C[p[i]]>=b and N-C[p[i]]>=a){
                viss[p[i]]=1;
                dfs1(q[i]);
                viss[p[i]]=0;
                miau++;
                dfs1(p[i]);
                break;
            }
        }
        int awa=0;
        for(int i=0;i<N;i++){
            if(res[i]==0 and awa<c){
                res[i]=3;
                awa++;
            }
        }
        return res;
    }
    
    for(int i=0;i<m;i++){
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
        B[p[i]]++;
        B[q[i]]++;
    }
 
    bool awa=false;
    for(int i=0;i<N;i++){
        if(B[i]==1){
            dfs(i);
            awa=true;
            break;
        }
    }
    if(!awa) dfs(0);
 
    vector<int>ans(N);
    for(int i=0;i<a;i++){
        ans[A[i]]=1;
    }
    for(int i=a;i<a+b;i++){
        ans[A[i]]=2;
    }
    for(int i=a+b;i<a+b+c;i++){
        ans[A[i]]=3;
    }
 
    return ans;


}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36