oj.uz

답안 #151541

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
151541 2019-09-03T14:06:35 Z Ruxandra985 Teoretičar (COCI18_teoreticar) C++14
91 / 130
 12000 ms 108068 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;
vector <pair <int,int> > v[400010],w[400010];
vector <pair <pair <int,int>,int> > mc;
int sol[500010];
int ciclu[800001];
int g[400010];
int q[800010];
int f[500010];
int m , st , dr;
void reset_all(){
    memset ( g , 0 , sizeof(g) );
    memset (f,0,sizeof(f));
    for (int i=1;i<=st+dr;i++){
        v[i].clear();
        w[i].clear();
    }
}
void dfs (int nod,int pus,vector <pair <pair <int,int>,int> > other[2]){
    int i,vecin,mch;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        mch = v[nod][i].second;
        //printf ("%d\n",mch)
        if (!f[mch]){
            f[mch] = 1;
            g[nod]--;
            g[vecin]--;
            other[pus%2].push_back(make_pair(make_pair(nod,vecin),mch));
            dfs (vecin,pus+1,other);
            return;
        }
    }
}
void pune (vector <pair <pair <int,int>,int> > mc , int &cul){
    /// pt chestia cu 2^x , o sa imparti muchiile mereu in 2
    int i,x,y,idx,gmax;
    /// verifici daca setul tau e independent

    reset_all();
    gmax = 0;
    for (i=0;i<mc.size();i++){
        x = mc[i].first.first;
        y = mc[i].first.second;
        //printf ("%d %d\n",x,y);
        idx = mc[i].second;
        v[x].push_back(make_pair(y,idx));
        v[y].push_back(make_pair(x,idx));
        g[y]++; g[x]++;
        gmax = max (gmax , g[x]);
        gmax = max (gmax , g[y]);
    }
    //printf ("\n\n");
    if ( gmax < 2 ) { /// e independent , pui cul peste tot
        if (!mc.empty())
            cul++;
        for (i=0;i<mc.size();i++){
            idx = mc[i].second;
            sol[idx] = cul;
        }
        return;
    }
    vector <pair <pair <int,int>,int> > other[2];
    /// vrei sa imparti muchiile in doua seturi astfel incat niciuna din primul set
    /// sa nu aiba aceeasi culoare cu una din al doilea set
    /// iei pur si simplu drumuri maximale si pui muchiile alternant,cum faceam
    /// si la euler
    /// trebuie sa am grija ca mereu sa pun ceva in ambele other uri

    for (i=1;i<=st+dr;i++){
        if (g[i]%2)
            dfs(i,0,other);
    }

    for (i=1;i<=st+dr;i++){
        while (g[i]){
            dfs (i,0,other);
        }
    }
    pune(other[0],cul);
    pune(other[1],cul);

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i,x,y,cul=0;
    fscanf (fin,"%d%d%d",&st,&dr,&m);
    int mi = m;
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        y+=st;
        mc.push_back(make_pair(make_pair(x,y),i));

    }
    cul = 0;
    pune(mc,cul);

    fprintf (fout,"%d\n",cul);
    for (i=1;i<=mi;i++)
        fprintf (fout,"%d\n",sol[i]);
    return 0;
}

Compilation message

teoreticar.cpp: In function 'void dfs(int, int, std::vector<std::pair<std::pair<int, int>, int> >*)':
teoreticar.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
teoreticar.cpp: In function 'void pune(std::vector<std::pair<std::pair<int, int>, int> >, int&)':
teoreticar.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<mc.size();i++){
              ~^~~~~~~~~~
teoreticar.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<mc.size();i++){
                  ~^~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:93:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&st,&dr,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:96:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 22648 KB Output is correct
2 Correct 28 ms 22648 KB Output is correct
3 Correct 28 ms 22648 KB Output is correct
4 Correct 23 ms 22648 KB Output is correct
5 Correct 24 ms 22648 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 22620 KB Output is correct
2 Correct 32 ms 22652 KB Output is correct
3 Correct 25 ms 22636 KB Output is correct
4 Correct 22 ms 22648 KB Output is correct
5 Correct 22 ms 22648 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 23160 KB Output is correct
2 Correct 33 ms 23268 KB Output is correct
3 Correct 39 ms 23324 KB Output is correct
4 Correct 28 ms 23160 KB Output is correct
5 Correct 26 ms 23160 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 23236 KB Output is correct
2 Correct 33 ms 23288 KB Output is correct
3 Correct 35 ms 23416 KB Output is correct
4 Correct 29 ms 23464 KB Output is correct
5 Correct 30 ms 23160 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 706 ms 58692 KB Output is correct
2 Correct 7361 ms 91192 KB Output is correct
3 Correct 1228 ms 74368 KB Output is correct
4 Correct 793 ms 86824 KB Output is correct
5 Correct 561 ms 75768 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 684 ms 58780 KB Output is correct
2 Correct 1259 ms 75008 KB Output is correct
3 Correct 2025 ms 83104 KB Output is correct
4 Correct 725 ms 77652 KB Output is correct
5 Correct 162 ms 38764 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 12077 ms 70180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1868 ms 108068 KB Output is correct
2 Correct 11367 ms 93760 KB Output is correct
3 Correct 3115 ms 86360 KB Output is correct
4 Correct 1002 ms 97156 KB Output is correct
5 Correct 710 ms 77632 KB Output is correct

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4768 ms 88076 KB Output is correct
2 Execution timed out 12085 ms 98816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4640 ms 88084 KB Output is correct
2 Execution timed out 12063 ms 98092 KB Time limit exceeded
3 Halted 0 ms 0 KB -