Submission #442465

#	Time	Username	Problem	Language	Result	Execution time	Memory
442465		emuyumi	Split the Attractions (IOI19_split)	C++17	Compilation error	0 ms	0 KiB

split

#include <bits/stdc++.h>

using namespace std;
#define ms(x,a) memset(x,a,sizeof x)
typedef long long ll;
const int mod=1e9+7, inf=0x3f3f3f3f, MAXN=1e5;

int n, a, b;
int mapping[3], sz[MAXN], rt[MAXN], T;
bool vis[MAXN];
vector<int> graph[MAXN], adj[MAXN], ans;
set<int> seen, cadj[MAXN];
int tot=0;

void build(int v){
    vis[v]=1;
    for (int to:graph[v]){
        if (vis[to]) continue;
        adj[to].push_back(v);
        adj[v].push_back(to);
        build(to);
    }
}

int dfs(int v, int p, int col){
    sz[v]=1; rt[v]=col;
    for (int to:adj[v]){
        if (to==p) continue;
        sz[v]+=dfs(to,v,col);
    }
    return sz[v];
}

void flood(int v){
    seen.insert(v);
    tot+=sz[v];
    if (tot>=a) return;
    for (int to:cadj[v]){
        to=rt[to];
        if (seen.count(to)) continue;
        flood(to);
        if (tot>=a) return;
    }
}

int centroid(int v, int p){
    for (int to:adj[v]){
        if (to==p) continue;
        if (sz[to]*2>n) return centroid(to,v);
    }
    return v;
}

void paint(int v, int p, int &cnt, int col){
    if (cnt) cnt--, ans[v]=col;
    for (int to:adj[v]){
        if (ans[to]||to==p) continue;
        paint(to,v,cnt,col);
    }
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q){
    n=N;
    vector<pair<int,int>> m={{A,1},{B,2},{C,3}};
    sort(m.begin(),m.end());
    for (int i=0;i<=2;++i) mapping[i]=m[i].second;
    a=m[0].first, b=m[1].first;
    ans.resize(n);
    for (int i=0;i<p.size();++i){
        int u=p[i], v=q[i];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    build(0);
    dfs(0,0,-1);
    int cen=centroid(0,0);
    rt[cen]=-1;
    for (int to:adj[cen]) dfs(to,cen,to);
    for (int i=0;i<p.size();++i){
        int u=p[i], v=q[i];
        u=rt[u], v=rt[v];
        if (u!=v&&u!=-1&&v!=-1){
            cadj[u].insert(v);
            cadj[v].insert(u);
        }
    }
    for (int to:adj[cen]){
        tot=0; seen.clear();
        flood(to);
        if (tot>=a){
            ans[0]=mapping[0], ans[1]=mapping[1];
            for (int i=2;i<n;++i) ans[i]=mapping[2];
            return ans;
        }
    }
    return ans;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    freopen("txt.in","r",stdin);
    freopen("txt.out","w",stdout);
    int n, m, a, b, c; cin >> n >> m >> a >> b >> c;
    vector<int> p(m), q(m);
    for (int i=0;i<m;++i) cin >> p[i] >> q[i];
    vector<int> ret=find_split(n,a,b,c,p,q);
    for (int x:ret) cout << x << " ";
    cout << '\n';
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i=0;i<p.size();++i){
      |                  ~^~~~~~~~~
split.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i=0;i<p.size();++i){
      |                  ~^~~~~~~~~
split.cpp: In function 'int main()':
split.cpp:101:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     freopen("txt.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
split.cpp:102:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     freopen("txt.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccjrkRxI.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKnubCL.o:split.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status