Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #524557

Source Code Expand

Copy
```#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>

using namespace std;
static const double EPS = 1e-9;
template<class T> bool INRANGE(T x,T a,T b){return a<=x&&x<=b;}
template<class T> void amin(T &a,T v){if(a>v) a=v;}
template<class T> void amax(T &a,T v){if(a<v) a=v;}
int ROUND(double x) { return (int)(x+0.5); }
bool ISINT(double x) { return fabs(ROUND(x)-x)<=EPS; }
bool ISEQUAL(double x,double y) { return fabs(x-y)<=EPS*max(1.0,max(fabs(x),fabs(y))); }
double SQSUM(double x,double y) { return x*x+y*y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))
#define NG (-1)
#define BIG ((int)1e9)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef long long ll;
typedef unsigned long long ull;

#if 1

class BipartiteMatching
{
public:
BipartiteMatching(int v) : V(v)
{
init();
}

void init()
{
G.clear();
G.resize(V);
match.clear();
match.resize(V);
used.clear();
used.resize(V);
}

{
G[u].push_back(v);
G[v].push_back(u);
}

int run()
{
int res=0;
fill(match.begin(),match.end(),-1);
for(int v=0;v<V;v++)
{
if(match[v]<0)
{
fill(used.begin(),used.end(),false);
if(dfs(v))
{
res++;
}
}
}

return res;
}

private:
const int V;
vector < vector <int> > G;
vector <int> match;
vector <bool> used;

bool dfs(int v)
{
used[v]=true;
for(int i=0;i<SZ(G[v]);i++)
{
int u=G[v][i];
int w=match[u];
if(w<0||!used[w]&&dfs(w))
{
match[v]=u;
match[u]=v;
return true;
}
}
return false;
}
};

int main()
{
int N;
scanf("%d ",&N);

vector <int> bx(N);
vector <int> by(N);
for (int i = 0; i < N; ++i)
{
scanf("%d %d ",&bx[i], &by[i]);
}

for (int i = 0; i < N; ++i)
{
vector <int> x;
vector <int> y;
for (int k = 0; k < N; ++k)
{
if(i!=k)
{
x.push_back(bx[k]);
y.push_back(by[k]);
}
}

const int S = SZ(x);
BipartiteMatching* bm = new BipartiteMatching(S*2);

for (int a = 0; a < S; ++a)
{
for (int b = 0; b < S; ++b)
{
if(a!=b && (x[a]==x[b] || y[a]==y[b]))
{
}
}
}

int a = bm->run();
if(a==S)
{
printf("OK\n");
}
else
{
printf("NG\n");
}

delete bm;
}

return 0;
}

#elif 1

vector < vector <pair <int, int> > > edgelist; // 隣接リスト
vector <bool> visited;			// 訪れたかどうか。双方向隣接リストになってるので、木を走査するときに、子→親に逆流するのを防がないといけないので必要。このフラグはnum_patternsとは別に必要。
vector <int> sumxor;

// vをルートとする部分木
void dfs(int v, int sum)
{
if(!visited[v]) {
visited[v] = true;
sumxor[v] = sum;
}

for (int i = 0; i < SZ(edgelist[v]); i++)
{
int next_v = edgelist[v][i].first;
if(!visited[next_v]) // 子だけ見るように
{
dfs(next_v, sum ^ edgelist[v][i].second);
}
}
}

int main()
{
int N,X;
scanf("%d %d ",&N, &X);

edgelist.resize(N);
visited.resize(N);
sumxor.resize(N);

for (int i = 0; i < N-1; ++i)
{
int x,y,c;
scanf("%d %d %d ",&x, &y, &c);
x--;
y--;
edgelist[x].push_back(make_pair(y,c));
edgelist[y].push_back(make_pair(x,c));
}

dfs(0,0);

map <int, int> mp;
for (const auto& a : sumxor)
{
mp[a]++;
}

ll ans = 0;

for (const auto& a : mp)
{
const map <int, int>::iterator it = mp.find(a.first ^ X);
if(it!=mp.end())
{
if((a.first ^ X) == a.first)
{
ans += (ll)a.second * (ll)(it->second-1);
}
else
{
ans += (ll)a.second * (ll)it->second;
}
}
}

ans /= 2;

cout << ans << endl;

return 0;
}

#elif 1

int main()
{
int N,M;
scanf("%d %d ",&N, &M);

vector <int> start(M), end(M);
for(int i=0;i<M;i++)
{
scanf("%d %d ",&start[i], &end[i]);
}

vector <int> rooms(300005);
for(int i=0;i<M;i++)
{
rooms[start[i]]++;
rooms[end[i]+1]--;
}

for (int i = 0; i <= N; ++i)
{
rooms[i+1] += rooms[i];
}

vector <int> saboren;
for (int i = 0; i <= N; ++i)
{
if(rooms[i]==1)
{
saboren.push_back(i);
}
}

vector <int> ans;
saboren.push_back(BIG);
for(int i=0;i<M;i++)
{
int lb = *lower_bound(saboren.begin(),saboren.end(),start[i]);
if(lb>end[i])
{
ans.push_back(i+1);
}
}

printf("%d\n",SZ(ans));
for (int i = 0; i < SZ(ans); ++i)
{
printf("%d\n",ans[i]);
}

return 0;

}

#else

int main()
{
vector <string> vs;
string s;
while( cin >> s )
{
vs.push_back(s);
}

for (int i = 0; i < SZ(vs); ++i)
{
if(vs[i]=="Left")
{
printf("<");
}
else if (vs[i]=="Right")
{
printf(">");
}
else if (vs[i]=="AtCoder")
{
printf("A");
}

if(i<SZ(vs)-1)
{
printf(" ");
}
}
printf("\n");

return 0;

}

#endif```

#### Submission Info

Submission Time 2015-10-10 22:27:46+0900 D - みんな仲良し高橋君 shindannin C++11 (GCC 4.9.2) 0 5490 Byte WA 3099 ms 498448 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:119:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d ",&N);
^
./Main.cpp:125:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d ",&bx[i], &by[i]);
^
```

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0.txt, example_1.txt, example_2.txt
Subtask1 0 / 30 bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_bubun_0.txt, random_bubun_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_bubun_0.txt, square_bubun_1.txt
All 0 / 70 bone_0.txt, bone_1.txt, bone_2.txt, bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, example_0.txt, example_1.txt, example_2.txt, handmade_0.txt, handmade_1.txt, handmade_2.txt, handmade_3.txt, komakai_0.txt, komakai_1.txt, komakai_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_0.txt, random_1.txt, random_bubun_0.txt, random_bubun_1.txt, renket_0.txt, renket_1.txt, smallrand_0.txt, smallrand_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_0.txt, square_1.txt, square_bubun_0.txt, square_bubun_1.txt, supersmall_0.txt, supersmall_1.txt, threeren_0.txt, threeren_1.txt, treebase_0.txt, treebase_1.txt, treebase_2.txt, example_0.txt, example_1.txt, example_2.txt
Case Name Status Exec Time Memory
bone_0.txt 3091 ms 469396 KB
bone_1.txt 3087 ms 490132 KB
bone_2.txt 3088 ms 463832 KB
bone_bubun_0.txt 3082 ms 458140 KB
bone_bubun_1.txt 3049 ms 95016 KB
bone_bubun_2.txt 3099 ms 498448 KB
example_0.txt 26 ms 796 KB
example_1.txt 27 ms 808 KB
example_2.txt 26 ms 800 KB
komakai_0.txt 3036 ms 9996 KB
komakai_1.txt 3035 ms 9364 KB
komakai_2.txt 3035 ms 9948 KB
komakai_bubun_0.txt 3039 ms 8840 KB
komakai_bubun_1.txt 3035 ms 9252 KB
komakai_bubun_2.txt 3035 ms 9244 KB
maxrand_0.txt 3035 ms 8596 KB
maxrand_1.txt 3034 ms 8604 KB
maxrand_bubun_0.txt 3034 ms 9112 KB
maxrand_bubun_1.txt 3037 ms 9100 KB
random_0.txt 3035 ms 1204 KB
random_1.txt 3034 ms 6044 KB
random_bubun_0.txt 3034 ms 1504 KB
random_bubun_1.txt 3035 ms 5740 KB
renket_0.txt 3037 ms 10132 KB
renket_1.txt 3035 ms 10128 KB
smallrand_0.txt 34 ms 928 KB
smallrand_1.txt 34 ms 808 KB
smallrand_bubun_0.txt 26 ms 800 KB
smallrand_bubun_1.txt 26 ms 804 KB
smallrand_bubun_2.txt 27 ms 932 KB
square_0.txt 3042 ms 59280 KB
square_1.txt 3041 ms 58648 KB
square_bubun_0.txt 3041 ms 58636 KB
square_bubun_1.txt 3043 ms 65628 KB
supersmall_0.txt 28 ms 728 KB
supersmall_1.txt 26 ms 728 KB
threeren_0.txt 3035 ms 10268 KB
threeren_1.txt 3035 ms 10136 KB
treebase_0.txt 3037 ms 10264 KB
treebase_1.txt 3035 ms 4892 KB
treebase_2.txt 3036 ms 9244 KB