제출 #133300

#제출 시각아이디문제언어결과실행 시간메모리
133300sealnot123게임 (IOI14_game)C++14
42 / 100
1072 ms13560 KiB
#include "game.h" #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; typedef pair<int,int> PII; typedef double D; typedef long double LD; const int N = 1505; int n, sq; int sqg[N][N], g[N][N], l[N], r[N]; int mk[N]; queue<int> bfs; bool check(int a){ int b = a*sq; int i, j = 1; for(i = l[b]; i < r[b]; i++){ mk[i] = 0; } mk[b] = 1; bfs.push(b); while(!bfs.empty()){ int u = bfs.front(); bfs.pop(); for(i = l[u]; i < r[u]; i++){ if(!g[u][i] || mk[i]) continue; j++; mk[i] = 1; bfs.push(i); } } return j == r[b]-l[b]; } bool check_group(){ int a = (n+sq-1)/sq; int i, j = 1; for(i = 0; i < a; i++){ mk[i] = 0; } mk[0] = 1; bfs.push(0); while(!bfs.empty()){ int u = bfs.front(); bfs.pop(); for(i = 0; i < a; i++){ if(!sqg[u][i] || mk[i]) continue; mk[i] = 1; j++; bfs.push(i); } } return j == a; } void initialize(int nn) { n = nn; LL i, j, a, b, c; LL ans = 1e18; for(i = 2; i <= n; i++){ c = (n+i-1)/i; a = c*(c-1)*n*n/2 + i*(i-1)*n*i/2; if(a < ans) ans = a, sq = i; } for(i = 0; i < n; i++){ for(j = i+1; j < n; j++){ a = i/sq; b = j/sq; if(a == b) g[i][j] = g[j][i] = 1; else sqg[a][b]++,sqg[b][a]++; } l[i] = i/sq*sq; r[i] = min(i/sq*sq+sq, (LL)n); } } int hasEdge(int u, int v) { if(u > v) swap(u, v); int i, j, a, b, res; a = u/sq; b = v/sq; if(a == b){ g[u][v] = g[v][u] = 0; res = check(a); if(!res){ g[u][v] = g[v][u] = 1; return 1; } return 0; }else{ sqg[a][b]--; sqg[b][a]--; if(sqg[a][b] != 0) return 0; res = check_group(); if(!res){ sqg[a][b]++; sqg[b][a]++; return 1; } return 0; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:87:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j, a, b, res;
         ^
game.cpp:87:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, a, b, res;
            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...