Submission #258981

#	Time	Username	Problem	Language	Result	Execution time	Memory
258981		peti1234	Split the Attractions (IOI19_split)	C++17	100 / 100	166 ms	18164 KiB

split

#include <bits/stdc++.h>

using namespace std;
const int c=100002;
int n, m, rf[c], si[c], hv[c], ans[c], f[c], pos, cent, t[4], ki, ko, na;
vector<int> sol, sz[c];
bool v[c], v2[c];
void dfs(int a) {
    v[a]=true, rf[a]++;
    for (int i=0; i<sz[a].size(); i++) {
        int x=sz[a][i];
        if (!v[x]) f[x]=a, dfs(x), rf[a]+=rf[x];
    }
    if (!cent && 2*rf[a]>=n) cent=a;
}
int holvan(int a) {
    if (!hv[a]) return a;
    int x=hv[a];
    hv[a]=holvan(x);
    return hv[a];
}
void unio(int a, int b) {
    a=holvan(a), b=holvan(b);
    if (a!=b) {
        si[b]+=si[a], si[a]=0, hv[a]=b;
        if (si[b]>si[pos]) pos=b;
    }
}
void dfs2(int a, int p) {
    v2[a]=true;
    if (a!=cent) unio(a, p);
    for (int i=0; i<sz[a].size(); i++) {
        int x=sz[a][i];
        if (!v2[x]) {
            if (a==cent) dfs2(x, x);
            else dfs2(x, p);
        }
    }
}
void dfs3(int a) {
    ans[a]=t[1], ki--;
    for (int i=0; i<sz[a].size(); i++) {
        int x=sz[a][i];
        if (!ans[x] && holvan(x)==pos && ki) dfs3(x);
    }
}
void dfs4(int a) {
    ans[a]=t[2], ko--;
    for (int i=0; i<sz[a].size(); i++) {
        int x=sz[a][i];
        if (!ans[x] && ko) dfs4(x);
    }
}
vector<int> find_split(int cs, int a, int b, int c, vector<int> p, vector<int> q) {
    n=cs, m=p.size(), ki=min({a, b, c}), na=max({a, b, c}), ko=n-ki-na;
    if (ki==a) t[1]=1;
    else if (ki==b) t[1]=2;
    else t[1]=3;
    if (na==c) t[3]=3;
    else if (na==b) t[3]=2;
    else t[3]=1;
    t[2]=6-t[1]-t[3];
    for (int i=0; i<m; i++) {
        int x=p[i]+1, y=q[i]+1;
        sz[x].push_back(y), sz[y].push_back(x);
    }
    for (int i=1; i<=n; i++) si[i]=1;
    dfs(1), pos=sz[cent][0], dfs2(1, f[cent]);
    for (int i=0; i<m; i++) {
        int x=p[i]+1, y=q[i]+1;
        if (si[pos]<ki && x!=cent && y!=cent) unio(x, y);
    }
    if (si[pos]>=ki) {
        dfs3(pos);
        dfs4(cent);
        for (int i=1; i<=n; i++) if (!ans[i]) ans[i]=t[3];
    }
    for (int i=1; i<=n; i++) sol.push_back(ans[i]);
    return sol;
}
/*
int b1, b2, b3, b4, b5;
vector<int> b6, b7, b8;
int main()
{
    cin >> b1 >> b2 >> b3 >> b4 >> b5;
    for (int i=1; i<=b2; i++) {int x; cin >> x; b6.push_back(x);}
    for (int i=1; i<=b2; i++) {int x; cin >> x; b7.push_back(x);}
    b8=find_split(b1, b3, b4, b5, b6, b7);
    for (int i=0; i<b8.size(); i++) cout << b8[i] << " ";
    return 0;
}
/*
9 10 3 3 3
0 0 0 0 0 0 1 2 4 5
1 3 4 6 7 8 2 3 5 6
*/

Compilation message (stderr)

split.cpp:93:1: warning: "/*" within comment [-Wcomment]
 /*
  
split.cpp: In function 'void dfs(int)':
split.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<sz[a].size(); i++) {
                   ~^~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int)':
split.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<sz[a].size(); i++) {
                   ~^~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int)':
split.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<sz[a].size(); i++) {
                   ~^~~~~~~~~~~~~
split.cpp: In function 'void dfs4(int)':
split.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<sz[a].size(); i++) {
                   ~^~~~~~~~~~~~~

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