Submission #130415

#	Time	Username	Problem	Language	Result	Execution time	Memory
130415		mirbek01	Simurgh (IOI17_simurgh)	C++11	Compilation error	0 ms	0 KiB

simurgh

    #include "simurgh.h"
    #include "grader.cpp"
    #include <bits/stdc++.h>

    using namespace std;

    const int N = 3e4 + 2;

    int p[N], sz[N], used[N];
    vector <int> g[N];

    int f_s(int v){
        return (p[v] == v)?v:p[v] = f_s(p[v]);
    }

    void u_s(int a, int b){
        a = f_s(a);
        b = f_s(b);
        if(a != b){
            if(sz[a] < sz[b])
                swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
        }
    }

    int tin[N], tout[N], timer;

    void dfs(int v, int pr){
        tin[v] = ++ timer;
        for(int to : g[v]){
            if(to == pr)
                continue;
            dfs(to, v);
        }
        tout[v] = timer;
    }

    bool upper(int a, int b){
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    }

    vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    	vector<int> r(n - 1);
        int m = (int)u.size();
        for(int i = 0; i < n; i ++)
            p[i] = i, sz[i] = 1;
        int pt = 0;
        for(int i = 0; i < m; i ++){
            if(f_s(u[i]) != f_s(v[i])){
                r[pt ++] = i;
                u_s(u[i], v[i]);
                g[u[i]].push_back(v[i]);
                g[v[i]].push_back(u[i]);
            }
        }

        dfs(0, 0);
        int cn = count_common_roads(r);

        for(int i = 0; i < pt; i ++){
            int a = u[ r[i] ], b = v[ r[i] ];
            if(upper(b, a))
                swap(a, b);
            int mx =  0, cntg = 0;
            vector <int> golds;
            for(int j = 0; j < m; j ++){
                if(used[j] == 2)
                    cntg ++;
                if(used[j])
                    continue;
                int cnt = 0;
                if(upper(b, v[j]))
                    cnt ++;
                if(upper(b, u[j]))
                    cnt ++;
                if(cnt != 1)
                    continue;
                int pre = r[i];
                r[i] = j;
                int kol = count_common_roads(r);
                if(mx < kol){
                    while(!golds.empty()){
                        int last = golds.back();
                        used[last] = 1;
                        golds.pop_back();
                    }
                    mx = kol;
                }
                if(mx == kol){
                    golds.emplace_back(j);
                } else {
                    used[j] = 1;
                }
            }
            if(cntg) continue;
            for(int j = 0; j < golds.size(); j ++)
                used[ golds[j] ] = 2;
        }

        pt = 0;

        for(int i = 0; i < m; i ++){
            if(used[i] == 2)
                r[pt ++] = i;
        }

        return r;
    }
/***
4 6
0 1
0 2
0 3
1 2
1 3
2 3
1 3 5
****/

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:79:21: warning: unused variable 'pre' [-Wunused-variable]
                 int pre = r[i];
                     ^~~
simurgh.cpp:97:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < golds.size(); j ++)
                            ~~^~~~~~~~~~~~~~
simurgh.cpp:59:13: warning: unused variable 'cn' [-Wunused-variable]
         int cn = count_common_roads(r);
             ^~
/tmp/cclf4eJu.o: In function `count_common_roads(std::vector<int, std::allocator<int> > const&)':
grader.cpp:(.text+0x2e0): multiple definition of `count_common_roads(std::vector<int, std::allocator<int> > const&)'
/tmp/ccRravxm.o:simurgh.cpp:(.text+0x480): first defined here
/tmp/cclf4eJu.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccRravxm.o:simurgh.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status